I haven't seen that kind of problem yet...
I currently have 2 Coldfire devices connected to my router (3com), as well as a couple of wired and wireless PCs and a Wii game console. All work fine, all have their own IP address assigned.
Always make sure every device has it's own unique MAC address, but you probably know that.
Try power cycling your router to reset it's client list and see if it makes any difference. Also, after power cycling the router, do the same with the coldfire board.