Had this problem on on the iPad and the iPhone. I did a complete restore on the iPad, that took a long time. I went to Itunes library on the MAC but it would still not update all the apps. When the restore was completed I still had over 100 apps that needed to be updated on the device directly. It did start to work correctly with the restore. I did not have to reset ibooks on the iPad.
On the iPhone what worked was going to ibooks and verifying that the account email and PW match what your using in itunes. It appears that it nows wants a email address vs just the acount ID. Onces I fixed that it started updating. I did not have to delete iBooks.
I performed all the other simple stuff like hard reboot, turn 3G on/off wiFi on/off but non of that worked for me.
Now if I could just get the iPhone 3 to not be SOOOO slow