You've probably figured it out by now, but I thought I would reply, JIC. I was having the same problem after losing some TV shows after my hard drive crashed. BTW, I did have my computer backed up using Time Machine but when I had the new hard drive installed...backup of the new drive erased all of my previous backups. Probably my own fault, but a major bummer.
Anyway, in the fine print on the support article (http://support.apple.com/kb/HT2519) it states that you have to delete the file (or the old link to it) in your iTunes library. Once I deleted that file (right click, Delete), the cute (barf) little iCloud icon appeared and I was able to redownload the purchases. I hope this helps, or that you have already solved your problem.