Remove your gmail account, then clear data/cache on playstore, service framework and download manager. Add your account again, and .restart.
Funny thing, I had to do this this morning. Second time it happens to me.
On my N4 there is no option to remove account, only add a new one? How do I fix the download error message that the OP described?
EDIT: I've found how to remove my Google account, I just hope it doesn't reset everything.