Just an idea, and I don't know if this will go over well, but....

How about a completely different desktop layout in portrait mode?
I mean: different contacts, different backgrounds, different widgets, the works.

This idea came from watching all of the n900 videos, where all the home screens for most of the users are already cluttered - this would give users 8 home screens to work with instead of 4. It would also let users arrange things as they want in either mode, since the widgets don't transfer anyway.
The *big* downside: If users want to access some widget they put in a landscape-orientation while holding the phone in portrait mode, they will have to rotate the phone, which will get kind of annoying after the first couple of times.

OR

When the phone is switched to portrait mode for the first time (or landscape mode for the first time), all the desktop widgets lose their positions and clutter at the bottom of the screen (annoying, I know). The user is then given an option on each thumbnail to "lock" its position in that location (kind of like drag-lock, but more location based). That way, say I wanted a widget in the upper left corner in both portrait and landscape orientation. I would just move it there in landscape and rotate the phone and "lock" it in place in portrait. It would be annoying the first time, but from then on out, the desktop would look like I wanted it to. This would solve the problem of making the software figure out where to put widgets and instead leave that choice to the user (and that's what we're all about, isn't it?).
The *slightly smaller* downside: widgets that span the whole screen in landscape will not work well at all. Widgets even slightly bigger than the width of the screen in portrait mode will break it. Possible solution: a toggle that would make such widgets automagically "hide" in portrait mode.

A "tweak" to the last solution I proposed: instead of having the widgets lose positions, the software could *attempt* to reorient them and indicate to the user that the layout is a temporary one that they can tweak and customize. I know quite a few people that wouldn't bother changing the order of the widgets around. It would also give a more polished "feel" to the rotation and not give the user a "darn, now why did I do that" sort of moment when the icons lose position.

Just throwing that out there...