The Kindle app on my iPhone 4s isn't downloading books
You say it suddenly started working again?

My best guess is that it was caused by GoDaddy's DNS servers going down.  This has caused generally odd behavior across the internet as many sites and URLs were 'forgotten' temporarily.  Many sites became unreachable.  

There's a chance the Kindle downloading mechanism relied on an address that was affected.