Perl, no date library: 160 159 155
sub f{($y,$m)=split/-/,@_[0],2;$y++if($m>'02-28');$y=($y+3)%400>>2;$y+=$y&&!($y%25);@r=(Tues,Wednes,Thurs,Fri,Satur,Sun,Mon);@r[(5*$y-($y/25&3))%7]."day";}
The real benefit of these date libraries is pushing off the length of the names of the days to someone else.
On the other hand, I think this is the only solution so far which works regardless of locale.