Maybe it's a FAQ but googling around I've found only a single suggestion that doesn't work.

Ubuntu 8.04.

I have 4 workspaces defined, I can name them if I use metacity, but if I switch to compiz (desktop effects = normal), my workspaces got renamed "Desk 1...4" and I cannot change it in any way. If I switch back to metacity they have the correct names again.

I've tried also to install the "advanced desktop effects" app, but I cannot find workplace names anywhere in the tons of configuration panels the application provide, also the "Find" function did not report anything useful.

The only suggestion I found googling was to change the names in metacity, then switch back to compiz, I've done it but as soon as compiz starts the workplace names are lost...