This happened to me also!
This is how I Fixed it-
SSH into your phone, go to /private/var/mobile/Library/Safari
and delete the History.plist.
then reboot your computer, and open up safari, surf a few pages, close it (in the multi-tasking bar also), reopen safari and start typing one of your surfed pages and see if it pops up in history.