You can correct the problem by using the Rotate effect.

First, create a new Project in Video Edit Magic. Choose "Let me specify the Project Dimensions". You'll have to pick project dimensions that are those of the finished movie, not the current one. For instance, if your rotated movie is 480x640, create a new Project with dimensions 640x480. If you don't know the pixel size of your rotated movie, you can look in Video Edit Magic's Collection window, under Video Info.

Now, use File, Open File to add your sideways movie to the Collection. Once it's there, click the Edit menu and the Add to Timeline. The movie will appear in Video Track 1.

Now, click the Effects tab in the Collections window. Locate the Rotate effect and drag it to the Effect Track under Video Track 1. Adjust the Rotation to turn the picture right-side-up. When you're done, click OK.

Use the Zoom Out button to zoom the timeline out, and drag the top-right corner of the Rotate effect until it is as long as the video. Now, use File, Make Movie to create a new movie, which will not be sideways.