Assuming you have AppleTV 2 or 3 (black models), are you checking under the TV Shows Purchased list or searching for them? Or are you looking under Compuetrs icon?
Are they in iTunes on computer and can you play them?
Are the purchases SD or HD? AppleTV 2 or 3 have an annoying habit of not listing SD content when browsing/searching if itunes store settings on AppleTv are configured for HD, but I'd expect them to show in Purchases.
For example when browsing the store on computer you may find an SD copy of a movie but no HD version - if Appletv is configured for HD store searches it doesn't offer SD if there's no HD available! AppleTv 1 used to just offer purchases in any format available.
Purchases 'in the cloud' are not guaranteed to always be there either should the studios decide to change their licencing to Apple, so always best to download a copy to itunes just in case.
AC