Sólo puedes tener un programita que use apt a la vez. Adept, synaptic, apt-get, aptitude, el gestor de actualizaciones, añadir o quitar programas, el gestor de controladores restringidos y, probablemente, alguno más lo usan en mayor o menor medida, así que mira si es eso lo que sucede.
Usan un fichero de bloqueo que sólo puede usarse una vez para impedir varios de esos programas usando apt. Si no tienes alguno usando apt, por lo que sea se te ha colgado alguno de esos programas y no ha borrado el fichero de bloqueo, tal vez borrándolo a mano se solucione.
No recuerdo cuál era el fichero, abre una terminal y escribe "sudo apt-get update" y te dará un mensaje de error diciéndote que no puede acceder a dicho fichero, luego lo borras (sudo rm /ruta/al/fichero). Si no estás seguro coméntanoslo antes de borrar nada.
Creo que no es una explicación muy sencilla, lo siento, a estas horas no estoy muy fino y no estoy muy puesto en (K)Ubuntu, pero como no contestaba nadie...
Saludos