I had the same problem. I can't get anything using PulseAudio to work, but I managed to get sound in Warzone 2100 by editing OpenAL's config file (/etc/openal/something) to use OSS instead. There are helpful comments inside the config file that tells you what to do.
Desktop: AMD Athlon X3 440 3.0ghz, 4GB RAM, Radeon HD4200, Windows 7 Professional 64-bit
Laptop: AMD Athlon X2 QL-64 2.1Ghz, 3GB RAM, Radeon HD3200, Windows Vista Home Basic 32-bit & Ubuntu 9.04 64-bit