That is completely normal behavior. While it does indeed uninstall the app, it does leave behind app data like settings, game saves, etc. This is also true for cydia apps. You can remove a cydia tweak and then later on go back and install it and all of the settings will be exactly how they were before you removed it. (I noticed this awhile back and coincidentally, just before seeing your post, I removed the latest bitesms beta version because it was chewing through my battery, rebooted my phone, deleted the beta repo, and installed the latest public release and all my settings are exactly the same.)
After removing an app, you can use iFile to navigate to the old application folder and you'll see these files still there. If you want absolutely no trace of an app, after you delete the app you need to use iFile or SSH into your phone and manually delete the remaining folders and files.
FYI, whenever you restore as new, all of these files are completely wiped off the phone. I am not sure what happens if you restore from backup since I've never done that. I always restore as new. Hope this helps!