Contact Apple billing support and/or the place you purchased the Mac to see if they can assist with resolving the server side issue. The OS updates are tied to the serial number, but the iLife apps go through a redeem process where the hardware identifier and your Apple ID get bond together, and the Apple servers apparently think a different account is set up for those apps on your Mac.
I'm assuming you have no idea and don't recognize the other Apple ID and it wasn't just a case of you accidentally redeeming the applications. I'm also assuming you can sign into the account you intended to redeem these apps. At worst, Apple or the seller should be able to gift you the apps to the correct account so you can get updates going forward if you (or someone else trying to be helpful) has made a mistake.
Here is what a Mac should look like before you have "accepted" the iLife apps by opening the App Store App and signing in and choosing Purchases (command-4) from the menu bar.
