Apenas para ilustração, essa questão da rede wifi está diretamente vinculada ao hardware do notebook. No meu caso, desde que migrei para o Ubuntu com um Eee PC 1000HA, no lançamento do 10.04LTS, nunca consegui que funcionasse direito, por causa da placa Atheros. O que resolveu o caso foi baixar o drive atheros do windows xp e usar o aplicativo ndiswrapper para configurá-lo como módulo wifi.
Assim, antes de mais nada, especifique o hardware em questão.