I have a Soltek mobo in my desktop PC, and I'm very happy with it.
Here's are some mobos that seem to forfill your needs.. All should be generally available and should have good Linux support.
MODEL: MS-6590 KT4 Ultra-BFISR
MODEL: SY-KT400 DRAGON Ultra (Plantinum)
MODEL: SY-KT333 DRAGON Ultra
Now I would buy first SOYO mobo, as SOYO generally offers good performance and high stability mobos for a reasonable amount of $$$.