Complete stab in the dark and I might seem a moron for suggesting it. Could the 'names' given to each iMac have anything to do with it? I'm backing up 2 almost identical MacBooks to a Time Capsule and have had no problems (backing up an iMac to it as well). Each MacBook has a different network name, and each HDD has a name.
The Time Machine seems to back up by HDD name rather than machine the HDD is in so I'm not sure if this is helpful or not.:o