I tried all of the prescribed remedies with no luck.
-I tried killing the safari app.
-I tried killing ALL of the running apps.
-I tried turning off/on the iPhone.
-I tried a hard restart.
No luck.
So after basically giving up, I decided to turn on iCloud backup for Safari so that if this happened again, I could at least hopefully retrieve my bookmarks from iCloud.
After doing this, all of my bookmarks that I had on my OLD phone before restoring to the new one reappeared. :-D
So I don't know if this maybe all had to do with the iCould setting on the new phone being set incorrectly by the Genius at the Apple store, or if it's just a weird bug, or what. But turning on iCloud backup for Safari worked for me in restoring my bookmarks.