Let's work backwards on this and see where we get to.
Firstly, the MBR that most backup software products talk about is nearly always a reference to the MBR boot code. This is just one part of what is called the MBR. This code is normally the first 300 bytes or so of the MBR. It is a very basic piece of software that reads the partition data (also in the MBR) and then loads the boot sector on the active partiton.
When you install Windows XP, or earlier, a *standard* version of the MBR boot code is written to the disk. When SP backups up a volume it also makes a copy of the full MBR, including this MBR boot code. If you restore back to the same HDD and select "restore MBR from backup", SP will simply overwrite the existing MBR boot code with the one from the backup image. If you select "restore an original Windows XP MBR", SP will just load the *standard* MBR boot code used during a Windows installation. Equally, if you boot into the Windows rescue environment and type "fixmbr", the utility will simply overwrite the existing MBR boot code with the Microsoft *standard* version. In other words there is no difference between the *standard* MBR boot code (original Windows XP MBR) and the one in you backup image.
So you may ask why SP, and other backup products, ask if you want to restore the MBR? The reason for this is that there are some applications actually change the *standard* MBR boot code with a modified one. Such applications/utilities include: Full disk encyption; snapshot applications; pre-boot menus and PCs that have a pre-installed "rescue" partition. Depending on your circumstances, you may or may not want this modified version, you may just want the old *standard* version. In your case, it doesn't make any difference. In fact, if you restored to the same HDD it would already have the MBR boot code on the disk.
One thing to keep in mind is that the MBR is not disk specific. In some cases it is, in fact, OS specific. Non-Windows OSs can add any MBR boot code they want, as long as it fits in to the allowed space. With the introduction of Vista even Microsoft changed the MBR boot code (they made it a few bytes longer to help support their bitlocker program).
Ok, so hopefully that answered the queston about the MBR.
Let's try and answer the question about Partition Magic. My guess is that there is nothing wrong with the restore. Partition Magic looks for partitions to start and end on sectors, rather than on cylinder. If it does not see this, it flags a disk error. Unfortunately there are no standards on this. SP just happens to use a default setting of "start/end on cylinder". Both options are valid. If you want to avoid Partition Magic saying there is a disk error you can change the SP restore option to "start on sector" and "end on sector".
Now on to the partition size. When you restore a backup image the image will normally include information about the original partition size.