Sounds like it could be a few different things:
1. There is some shred of paper somewhere that is jamming your paper feed just enough to be a problem. (not likely)
2. Are you pulling on the paper by hand or hitting the "feed" key? Manually pulling on the paper is not recommended and can cause issues.
3. Check the bottom of the paper well (the cavity the paper sits in) and ensure nothing is laying in the bottom of the well. I've seen where the plastic spindle has remained in the well when inserting a new roll and has caused issues.
If you have tried and/or observed that none of the above is the culprit, please describe what steps you have to take to make it start printing again? I'm also assuming you tried just hitting the EC key when the error appears?