Historic answer only. Spectacularly out of date.
Please note that this answer is now hugely out of date/
This answer is only a historical curiosity.
Exciting news! As discovered by Andrew below, this problem has been fixed by Apple in 4.0+.
It would appear it is NO longer necessary to force the size of the view on every view, and the specific serious problem of landscape "only working the first time" has been resolved.
As of April 2011, it is not possible to test or even build anything below 4.0, so the question is purely a historic curiosity. It's incredible how much trouble it caused developers for so long!
Here is the original discussion and solution. This is utterly irrelevant now, as these systems are not even operable.
It is EXTREMELY DIFFICULT to make this work fully -- there are at least three problems/bugs at play.
try this .. interface builder landscape design
Note in particular that where it says "and you need to use shouldAutorotateToInterfaceOrientation properly everywhere" it means everywhere, all your fullscreen views.
Hope it helps in this nightmare!
An important reminder of the ADDITIONAL well-known problem at hand here: if you are trying to swap between MORE THAN ONE view (all landscape), IT SIMPLY DOES NOT WORK. It is essential to remember this or you will waste days on the problem. It is literally NOT POSSIBLE. It is the biggest open, known, bug on the iOS platform. There is literally no way to make the hardware make the second view you load, be landscape. The annoying but simple workaround, and what you must do, is have a trivial master UIViewController that does nothing but sit there and let you swap between your views.
In other words, in iOS because of a major know bug:
[window addSubview:happyThing.view];
[window makeKeyAndVisible];
You can do that only once. Later, if you try to remove happyThing.view, and instead put in there newThing.view, IT DOES NOT WORK - AND THAT'S THAT. The machine will never rotate the view to landscape. There is no trick fix, even Apple cannot make it work. The workaround you must adopt is having an overall UIViewController that simply sits there and just holds your various views (happyThing, newThing, etc). Hope it helps!