Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Is your Safari search engine set to Yahoo or Google?
If it is Yahoo, try setting it to Google.
Settings > Safari > Search Engine

I'm just making a wild guess. See if that does anything?
 
The search engine is set to Google, I tried setting it to yahoo and then back to google with no luck. I also just discovered that the phone isn't saving my history either. It seems like the permissions to whereever the safari info is saved are messed up.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.