What version of Premiere Pro are you using? If you are using a late enough version, is the Mercury Playback Engine GPU Acceleration (CUDA) enabled?
Open a project
Click on Project
Click on Project Settings
If you see Mercury Playback Engine software only then your video card is not recognized as a card that will use CUDA. However, there may be a work around for this from VideoGuys: http://www.studio1productions.com/Articles/AfterEffects...
I have noticed a huge difference in rendering times when I use the GPU enabled rendering vs the software only (desktop has GPU rendering while my laptop does not).
Corel Video Studio Pro X5 might do the job for you. Looking at the tech specs it supports an AMD processor.