I compiled the regex library with:
> bjam.exe -sTOOLS=mingw -sMINGW_ROOT_DIRECTORY=D:\Dev-Cpp
>
> When linking my project with the generated library
> (libboost_regex-mgw-d-1_33.lib), I get:
>
> ../sources/cmdline.o(.text+0x6fe9): In function `_tcf_1':
> d:/Dev-Cpp/Bin/../lib/gcc/mingw32/3.4.2/../../../../include/c++/3.4.2/bits/basic_string.h:257:
> undefined reference to
> `boost::re_detail::cpp_regex_traits_implementation<char>::init()::null_string'
> ... etc....
>
>
> Does that mean I should try using STLPort or ?

Works OK for me (with the latest MinGW stable releases / gcc-3.4.2).  One 
thing you could check:  what command line did you use to link?  You did 
place the regex library *after* any object files that depend upon it didn't 
you?

John. 
Sorry, I don't get the ordering issue you mention...

I used Dev-cpp for creating the makefile but that makes little difference.
Anyway, here is the executed linking command line for the "grep" example:

g++.exe -D__DEBUG__ grep.o  -o "regex_grep.exe" -L"lib" ../../../../bin/boost/libs/regex/build/libboost_regex.lib/mingw/debug/libboost_regex-mgw-d-1_33.lib ../../../../bin/boost/libs/program_options/build/libboost_program_options.lib/mingw/debug/libboost_program_options-mgw-d-1_33.lib  -g3 

The OUTPUT being:

grep.o(.text+0x5c69): In function `_tcf_1':
d:/Dev-Cpp/Bin/../lib/gcc/mingw32/3.4.2/../../../../include/c++/3.4.2/bits/basic_string.h:257: undefined reference to `boost::re_detail::cpp_regex_traits_implementation<char>::init()::null_string'
grep.o(.text+0x5d1b): In function `_tcf_0':
d:/Dev-Cpp/Bin/../lib/gcc/mingw32/3.4.2/../../../../include/c++/3.4.2/bits/stl_tree.h:460: undefined reference to `boost::object_cache<boost::re_detail::cpp_regex_traits_base<char>, boost::re_detail::cpp_regex_traits_implementation<char> >::do_get(boost::re_detail::cpp_regex_traits_base<char> const&, unsigned int)::s_data'
.
.... ETC ....
.
collect2: ld returned 1 exit status


Thanks.
Arno