I am having problems building the Boost 1.33.1 libraries using gcc 4.0.2
on a Linux system. I have used boost:regex for years, but am upgrading
to gcc 4.

Sounds like a compiler issue. Your test program works here on g++ version 4.0.3 20060128 (prerelease) (Debian 4.0.2-8) and 1.33.1. I do seem to have ICU enabled as well though.

[11:22] cae @ tela 534% g++ -o sp20 sp20.cpp -lboost_regex
[11:22] cae @ tela 535% ./sp20
[11:22] cae @ tela 536% ldd sp20
        linux-gate.so.1 => (0xffffe000)
        libboost_regex-gcc-mt-1_33_1.so.1.33.1 => /usr/lib/libboost_regex-gcc-mt-1_33_1.so.1.33.1 (0x40028000)
        libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x400d1000)
        libm.so.6 => /lib/tls/libm.so.6 (0x401ae000)
        libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x401d4000)
        libc.so.6 => /lib/tls/libc.so.6 (0x401df000)
        librt.so.1 => /lib/tls/librt.so.1 (0x40316000)
        libicui18n.so.34 => /usr/lib/libicui18n.so.34 (0x4031f000)
        libicuuc.so.34 => /usr/lib/libicuuc.so.34 (0x4043e000)
        libpthread.so.0 => /lib/tls/libpthread.so.0 (0x40548000)
        /lib/ld- linux.so.2 (0x40000000)
        libicudata.so.34 => /usr/lib/libicudata.so.34 (0x4055a000)