All right, and if there aren't any bookmarks and you know your computer is still set up to sync to the cloud too, did you try a reboot? Next, I would re-sync (wifi) to iTunes and see if that helps matters.
Reboot of phone worked. All bookmarks are back. Weird that that hapened to begin with.