Any chance you upgraded from an older device, like the Pearl? Another user lost the "Add Folder" menu option on their Curve after doing a restore/upgrade from Pearl data, here's the thread:

Bookmarks - no "add folder" option?

Perhaps you're seeing the same issue manifested in a different way?