I had this issue too. I ended up having to do a factory reset from within the nes classic menu. It cleared out whatever files where stuck in there ( including old savestate files) and then it loaded up just fine.
So after doing the factory reset within the nes classic menu, you still had all your games, but just had to select language and all your save states were gone. Folders and everything were intact?
EDIT: All save states are now gone. Not a big deal as I don't do much saving, but if you are having problems with errors, due to save states from previous games this will help.
Last edited by DR1001,