The problem seems to be with VC7.0's implementation of the standard library. In particular, there's another overload of std::_Iter_cat that takes a std::iterator as a parameter; this overload wasn't considered by the compiler when it generated the error message above.
It looks like instead of relying on iterators to define typedefs for iterator_category, value_type, et al., the library assumes that an iterator must actually derive from std::iterator. This assumption has been removed from the library implementation in VC7.1.
That's correct, I should have derived from std::iterator or used Boost's own iterator adapters I guess, I'll look into fixing this
Given all of this, it seems like my options are to modify my copy of regex_iterator.hpp, modify my copy of <xutility>, or hope that someone has a third option. (Upgrading to vc7.1 is not an option this week. :-)
I'll post the patch when I have it, if that helps, John.