CS4 was unable to export and encode a video after upgrading from CS3. The error message indicated the the file could not be found. To fix this problem do the following. Create a short cut to adobe premiere pro (executable program) named "Premiere" Then place the short cut in the folder C:Program Files/Common Files/Adobe/dynamiclink After doing this my version worked fine.
Good of you to post this solution that worked for you, but I think something else was wrong on your system. On my system it is not needed and I have both CS3 and CS4 installed and working without problems.
The problem mainly occures when one then removes the CS3 version of Adobe Premiere. I have found a tech note on this problem at: