Have ios 5 on ipads and iphones and contact changes made on them appear on each other but not my Imac. Also if I make a new contact on Imac it is not sent to pads or phones.
If so, turn off the contact synching (leaving your other synching on). Reboot the machine and then turn it back on again and it should fix the problem.
If you're not using Lion, try it anyway, you never know!