No, you should not have to pay for it again.
Try a rest: Simultaneously hold down the Home and On buttons until the iPad shuts down. Ignore the off slider if it appears. Once shut down is complete, turn the iPad back on using the On button. In some cases it also helps to double click the Home button and close all apps from the tray before doing the reset.
I am in the same boat with my wife's iPhone 4. We have restarted it using both the 'rest' method and the normal method with the slider etc. I have tried the Time and Date trick where you set the date to a few years in the future or a few years in the past and no dice. I have tried syncing her phone to her computer and that did not update any of the apps. I have been largely unsuccessful. Any comments of knowledge on the issue would be helpful. It also seems that she is having an issue with her iMessage today. I cannot tell if that is related or not as she is still at work. Any help would be great on this.
The problem has sort of solved it self, so it's no longer an issue.
I think that Apple has "done something" in the Appstore, but i noticed the following prior to the problem being solved, which might be an inspiration to others:
A similar problem existed in the Podcast application as items i subscribed to, wouldn't download when i pressed the "Down" button, that usually starts a download. Shutting down Podcast and restarting it, usually solved the problem after 2-4 tries.
Within Appstore in the "Purchased" section where you can see all apps downloaded, the problem with update is the same as in the "Update" section, described earlier.
I then tried to "disconnect" my Apple ID, and within Appstore start downloading some random free app, at which ID and password is requested, and after entering that, the download proceeded without problems.
While still in Appstore (and the entered ID + password still "active"), i then in the "Purchased" section, i could suddently download the updates waiting, one at a time, but with the "twist" that i in most cases had to try 2-5 times before the download started.
After that updates started working again, but still i had to try several times, and then after a week or so, it was back to normal where updates starts downloading immediately - problem solved.