I'm new to linux and would like to build a system. However, finding a basic motherboard that works "out of the box" appears to be a problem. Does anyone have any recommendations?

I think Linux builders preffer brands such as ASUS or MSI combined with AMD processors. Which one have you tried?

Recently I've looked for mobo with Z68 chipset for my new desktop. With classic BIOS (non-UEFI in order to prevent possible installation problems). After several days of searching I found Foxconn Z68A-S mobo.
Works fine for me. I've tried a lot of different linux distros (gentoo, mint, mageia, debian, openSUSE) without problems.
Currently I have Debian Squeeze and WinXP installed in dual boot.
My setup is: Z68A-S mobo, Core i3 2120 CPU, 4Gb RAM, GeForce GTX 550Ti video.

Go to the source.

http://www.ubuntu.com/certification/

https://wiki.ubuntu.com/HardwareSupport

That sources are out of date (last edited at 2010) and recommends outdated hardware

The basics on most Intel or AMD motherboards will work 'out of the box'. CPU support, memory, etc. should never give you issues. Sound and networking chips can be dodgy with linux, but generally they are fine as well.

The only time you really have issues with linux and motherboard parts is from stupid addon SATA controllers, wireless network adapters, etc..

Brand will make zero difference. Intel works as well as AMD does (though I get tend to get AMD CPUs for various reasons).

That translates as "buy big branded hardware from companies that have paid canonical to get 'certified'". While its not as bad as it was in the past, the 'ubuntu certified hardware list' is still pretty much a joke.....

Must say, I go for an ASUS board when its time to upgrade. Having said that, most new boards will work with Ubuntu or any other distro.