Just had a bit of luck with this one.
I logged into the GUI as root, and added another redhat start menu button to the toolbar. Saved the changes and logged out.
Logging in as a normal user showed that my toolbar had returned.
This looks to be some sort of bug with the saving of desktop configurations, and I guess making the changes as root caused something to be rewritten.
Hope this helps