@Tormod Volden. I had a fellow at my LUG today having this issue. He has an R200 based chip (Radeon Mobility 9000). This is an Ubuntu Karmic Nebook install, all updates as of today.
The updated mesa from x-swat's x-updates did not solve the issue.
The only solution we found was to create an xorg.conf file to set NoAccel to true. It works and is stable now, but is rather extremely slow.
What other information do you need from his machine? Any other things you would like to try?