Perl, no date library: 160160 159 155
sub f{($y,$m)=split/-/,@_[0],2;$y++if($m>'02-28');$y=(($y+3)>>2%400>>2;$y+=$y&&!($y%25)%100;@r=;@r=(Sun,Mon,Tues,Wednes,Thurs,Fri,Satur,Sun,Mon);@r[(2+5*$y+4*($y/25&3)+2*(5*$y-($y-1)/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.