I now have it up and running
I'm using Ubuntu on all machines. I found out what was making my troubles, and it was the old databases on the other machines that made it now work for me.
My second problem was the thumbnails, only the server had thumbnails. So I copied the thumbnails folder onto the other machines, and everything looked fine until media was added and only the machine that found the new media had thumbnails.
Since I always have 1 computer running as a Tvheadend server, and it has the mysql database, I shared the XBMC folder too.
Here is a quick howto:
Follow the first guide to get the database running
On the server, right click the .xbmc folder in nautilus and share it as xbmc. It will ask for permission to install some required software.
On the rest of the computers install SMBFS:
sudo apt-get install smbfs
Edit /etc/fstab and add this line:
//servername/xbmc /media/xbmc smbfs username=xxxx,password=xxxx 0 0
Change the servername and user/pass
Reboot and you will have a drive called XBMC. Open it, enter the userdata folder and rightclick Thumbnails and select Make Link.
Copy the link to your .xbmc/userdata/ folder.
Delete the old ./XBMC/userdata/Thumbnails and rename the link to only Thumbnails.
Now all computers in my house use the same Thumbnails folder and mysql database. If media is added, the first computer to scan will add it and it works on all computers.
Another tip, copy the sources.xml from the servers userdata folder, or make a symbolic link if you want all machines to have the same sources...