Você pode encontrar a maioria dos compatíveis aqui: link inclui os PCI, USB e o Mini PCI-E você quer procurar.
Lembre-se que cerca de 99% da compatibilidade vem do Kernel e não da Distro. A maioria das distro incluirá algumas placas wireless e talvez os drivers de terceiros, mas se você quiser olhar para ter certeza, eu recomendo que você verifique primeiro qual versão do Kernel a distro que você quer está usando. Já que você está aqui, eu suponho que estamos falando sobre o Ubuntu 11.04 que tem a versão do kernel 2.6.38 . A quantidade de drivers de rede pode ser encontrada aqui: link para cada versão do kernel. uma vez que a rede é uma das principais características do Linux e é uma das mais trabalhadas, você tem uma chance muito grande de comprar uma placa wireless conhecida. (Quando eu digo conhecido, quero dizer algo como RaLink, Broadcom, etc.) .. em vez de algum cartão de empresa estranho como "Chicken Little Wireless Card Edição French Fries"
Também já instalei 3 Acer Aspire One e eles funcionam 100%. Então, talvez seja um problema de hardware que o Linux também possa lhe dizer através de vários comandos (como o dmesg, por exemplo).