The location of the widgets are somehow stored by the OS. Could it be a start to have two separate location storages, one for portrait and one for landscape? After adding a widget and rotating the screen the first time, the user can move the new widget to suit also the other orientation. This would mean the user has to configure the homescreen for both orientations and might be a bit annoying if a lot of widgets are added in one go, but at least when adding only one I don't think this would bug me as a user too much.
Cons, from the top of my head: * Width of widgets would be limited to 480 pixels, minus whatever padding is needed.