Also, it should be stated that when using the lens correction, PS assumes that the center of the images circle is in the center of the image. If you did any shifting, this is not the case. So I always make a new blank file of the same proportion but larger, then transpose the image into the blank new one, move the images within this so the center of the image circle is in the center of the new image, and then preform the lens correction and other stuff tesfoto listed.
Also, I always tend to correct the perspective optically which gives the best results and use the above method just to make sure everything is straight and lined up.