10.8 Safari Bug?

I moved from 10.6 to 10.8 with the recent purchase of a MacBook Air and Safari doesn't seem to be keeping track of my pages visited. The scenario is as follows:

-Open new window in Safari
-Using top search bar (mine is set to Google), search for weather
-Click on weather.com, page back. Click on accuweather, page back. Click on weather.gov, page back.
-Quit Safari
-Reopen Safari. Search again for weather.
-Notice not all links have switched from "blue" (unread) to "purple" (read).

Replicating this on my MBP with 10.6 all of the links I've clicked on are purple.

Apple Support has no idea what is causing this. I created a guest account on the Air and was able to recreate it.

Any ideas?

I'll also add that the visited pages ARE showing up in the "History" menu.

I did a fresh install of ML and didn't change any settings on Safari and experienced the same issue. Apple Support still claims it is on Google's end. Ugh.

To give everyone an update, I spoke with a senior Apple adviser today and he watched me recreate the issue on my screen. We weren't able to resolve it, so I logged the system stuff and he is sending it on to the programmers for examination.