iMovie and the other iLife apps used to be paid-for except with a new Mac, and when the App Store was introduced, it registered the Mac's serial number with your App Store account to allow you to download iMovie etc. for free.
These days, these apps are actually free anyway. The problem in your case is that you still have the old binary around, and this contains the App Store receipt with your old App Store Apple ID.
- Make sure you have a backup of the iMovie app just to be sure, (e.g. Time Machine, or just copy the app to an external HDD or USB stick)
- Then quit the App Store app if it's running and delete iMovie from the Applications folder.
- Eject any external media that have the iMovie app on as well, so the App Store app can't find any existing copies to update.
- Open the App Store, make sure you're logged in with your correct Apple ID.
- Find iMovie in the store (just search for it), and hit "Get". This will redownload the latest version of iMovie for free, using your new Apple ID.
Step 3 is crucial, if the App Store can find an existing copy of the app it will try to update it again, running into the same problem as before.