It would help to know what OS you are using.
There are usually no problems running different versions of AE on the same machine. I've got CS2, CS3, CS4 and AE7 on the same machine. There have been licensing issues and when you've had demo or beta versions installed. These are covered in the Adobe trouble shooting docs.
Did you re-install all other Adobe products as well? If not, then that may be the problem. Uninstalling/ reinstalling only one of them messes with MediaCore and certain otehr functions. The quick fix is to download the manuala (!) update packages for After Effects, Premiere Pro/Encore and Adobe Media Encoder from the support pages and run them. This usually bends things in place. If not, then you will probably have to uninstall again, this time including every Adobe app, use the CS4 Clean Script and reinstall.
I was afraid that I might have to uninstall everything again in order to use the clean script, but may be worth it for peace of mind.
Hey, doesn't my system info appear in my profile. I always get replies asking me what Windows version, etc. I am using. I shouldn't have to furnish that info with every post.