Har problem, söker paket.

Din guide behandlar Debian, jag rekommenderar att du följer en guide för Ubuntu istället, t.ex.: http://doc.gwos.org/index.php/Latest_Nvidia_Dapper. På det sättet slipper du dina problem, utan kan använda en färdig version istället.

Vill du trots allt ha kernel headers ska följande kommando funka:
sudo apt-get install linux-headers-`uname -r`

Observera att jag inte använder *Ubuntu själv, min enda erfarenhet av distron är att slänga in en installation på min flickväns dator.