The first thing to do is go into
Add-ons > Extensions > StumbleUpon: Preferences > Search & Tagging and make sure the "Save favorites & tags to a Firefox bookmar folder" checkbox is still checked.
If it is, try clicking the "Download Favorites" button to force a full re-download.
If that doesn't fix it, you may need to build a new Firefox profile to get things back on track. I know, on my system, upgrading from Firefox 3.6 to Firefox 4 broke my existing profile so badly that the address bar wasn't updating when I clicked links.
Thankfully, you can export your bookmarks and manually copy supplemental extension data like installed Greasemonkey scripts and Stylish userstyles if that proves necessary.