Enter the number 40226 in a previously unused cell (not one of your problem cells).
Now format it as a date. If it shows 17 Feb or similar, then your date formatting works, and as Mike suggested you likely have dates / times entered as text.
Excel has to recognize what is entered as a date or time, and it can be quite picky about what it accepts. If it doesn't recognize the entry as a date or time it leaves it as text which will not respond to format changes.
If it recognizes what is entered, as a date or time, Excel automatically converts the text to a number which it stores, but displays it according to the date/time format.
40226 is Excel's number for 17 Feb 2010. The numbers started at 1 for 01 January 1900.