I don't have an answer for you, but maybe I can point you in the right direction.
Searching on the error message, the best hits I got were in the Apple Support Communities. There's a user Pondini who's very knowledgeable about Time Machine. In fact, they have put together some pages containing in depth Time Machine troubleshooting... http://pondini.org/TM/Troubleshooting.html
In this Apple thread by a user with the same problem as yours, Pondini recommends first deleting Time Machine's InProgress package file from the backup drive (step A10) and then repairing the external drive (step A5). Here's the thread... https://discussions.apple.com/thread/4189896?start=0&tstart=0
The OP doesn't reply back to say if it worked or not, but I'd say it looks like a place to start.
If it were me, and the fix didn't work, and I wanted to keep the old files, I'd get a new, larger external. They're reasonably inexpensive nowadays.