This only seems to remove the app icon. For example, I'm using the categories app and it recently spewed out all of my apps onto my springboard while also keeping them in my categories folders. I "removed" the app through cydia and it only removed the icon. The folders are still there. All my apps have been doubled. I can't completely remove the app and then reinstall it. What gives?
Before you removed the categories folders, you should have removed them in categories first. But you will have to restore and re-j/b the phone as blkcadi has stated above.