Check for available downloads only works on things you have never downloaded. You can go in and manually search for the previous purchases and manually download -- BUT this will only work on some purchases. Apple added the ability to redownload purchases (I can't remember when) but some stuff purchased before they added this feature maybe SOL.
Go to the iTunes Store, log into your account, and click the Purchases link under the Quick Links. From there you should be able to re-download some or all of your purchased content. Note that not all content has been licensed for re-downloading in all countries at this time. You can see what content you can download here:
You can also re-download content using an iOS device.
For full instructions, see: