The same thing happens to me when I copy data from another source. I have found that the data is actually formatted as text, and has an apostrophe before the date. If this is what's happening to you, you can can remove it using EDIT-REPLACE. In "Find What:" you can put the apostrophe ('), and in "Replace With" you can leave blank. Then select "Replace all".
The data does come from Access but it does not have an apostrophe in front of it.
The only other things that I can think of is if there is a space before your date begins ie: " 5/2/99". Replace will work with this also.
If the date was formatted as text, for some reason Excel still sees it at text even if you format it (I have this problem sometimes with data from access). You can tell the problem by hitting F2 and then enter after you format it. If it changes to your desired format after doing this, then that is your problem. I'm not sure if this is the best way to fix it, but if you type a zero in a blank cell, copy it, and then Paste special over your data, and select values and add, it will change it from text. I'm sure this is probably not the best way, but it does work.
You could also try highlight the column and going to data - text to columns.
Hit next, next again, select date MDY and finally finish. This would hopefully "clean it up".
good luck.