#PHP, 104 bytes

function f($s){for($y=$s-(substr($s,5)<"02-29");!date(L,$t=strtotime(++$y."-2-1")););return date(l,$t);}

breakdown

for($y=$s-; // "-" casts the string to int; decrement year if ...
 (substr($s,5)<"02-29") // ... date is before feb 29
 !date(L, // loop while incremented $y is no leap year
 $t=strtotime(++$y."-2-1") // $t=feb 01 in that year (same weekday, but shorter)
 );
);
return date(l,$t); // return weekday name of that timestamp

date(L): 1 for leap year, 0 else
date(l): full textual representation of the day of the week

PHP, 104 bytes

function f($s){for($y=$s-(substr($s,5)<"02-29");!date(L,$t=strtotime(++$y."-2-1")););return date(l,$t);}

breakdown

for($y=$s-; // "-" casts the string to int; decrement year if ...
 (substr($s,5)<"02-29") // ... date is before feb 29
 !date(L, // loop while incremented $y is no leap year
 $t=strtotime(++$y."-2-1") // $t=feb 01 in that year (same weekday, but shorter)
 );
);
return date(l,$t); // return weekday name of that timestamp

date(L): 1 for leap year, 0 else
date(l): full textual representation of the day of the week