ifconfig -a
するとどう？eth0の代わりにeth1が認識されてたりしない？
だとすると、使っているディストリビューションにもよるけど、udevが悪さしてる可能性が大。

Debianなら、
http://repse.blogspot.com/2009/06/colinux.html
とかの人のやつが参考になると思う。