Nathan,
I feel that you have set PortraitViewController as the rootViewController of UINavigationController. I also believe that you are restricting the PortraitViewController's orientation only to UIInterfaceOrientationPortrait only in the shouldAutorotateToInterfaceOrientation method. If so then, any view controller that you push will have the orientation of the rootViewController itself unless you are not changing the device orientation by rotating your device.
So if you need the LandscapeViewController in the UIInterfaceOrientationLandscapeRight orientation then just allow this in shouldAutorotateToInterfaceOrientation: method and don't screw things by explicitly setting the device orientation.