Se me ocurren varias preguntas sobre el asunto y la respuesta de esas preguntas puede ser importante para resolver el problema.
-----
Para configurar un dispositivo wireless en linux lo que importa es saber el chip que tiene (atheros, prism, realtek, broadcom, zydas, ralink ...) no la marca del fabricate (SMC, Linksys, Edimax, Sitecom, Conceptronic, Senao, BLUMENT ...). Para averiguar eso hay por lo menos un par de comandos: lspci y lsusb.
La primera pregunta que se me ocurre es: ¿ El dispositivo wireless que intentas configurar es PCI o es USB ? por lo que comentas tiene pinta de ser PCI (hablas de comandos como lspci o update-pciids).
Si es PCI el comando lspci sirve para _ver_ los dispositivos PCI conectados en esa máquina (pero _ver_ el dispositivo no es sinónimo de estar ya configurado y funcionando). Si es PCI estaria bien que apuntaras la salida del comando lspci (si hace falta en un papel) y nos la pegaras aqui en el foro.
Si es USB el comando lsusb sirve para _ver_ los dispositivos USB enchufados en esa máquina (pero _ver_ el dispositivo no es sinónimo de estar ya configurado y funcionando). Si es USB estaria bien que apuntaras la salida del comando lsusb (si hace falta en un papel) y nos la pegaras aqui en el foro.
-----
Sobre la distribución de linux: has dicho que usas Ubuntu pero no has dicho que versión (... 7.04, 7.10, 8.04, 8.10 ...) ni que versión de kernel lleva.
La segunda pregunta (y tercera) que se me ocurre es: ¿ Qué versión de Ubuntu estas usando ? ¿ qué kernel lleva ?
La versión de Ubuntu la puedes ver en varios sitios: durante el arranque de Ubuntu sale, en el archivo iso que te descargaste para hacer el CD sale, si en lugar de hacer tu el CD lo has pedido esta serigrafiado en una de sus caras y la versión sale... Para saber la versión del kernel tecleando uname -a lo ves, estaria bien que apuntaras la salida de ese comando (si hace falta en un papel) y nos la pegaras aqui en el foro.
-----
Olvidate temporalmente del comando update-pciids pq ese comando solo funciona como root (estando en Ubuntu hay que poner sudo delante) solo funciona si ya tienes conexión a internet (por lo que comentas todo apunta a que no tienes conexion a internet en linux de ningun tipo) y solo sirve para ver bien la salida del comando lspci (que como comenté antes es un comando que solo sirve para ver, no configura nada).