There may be something going on with the properties. Does the problem persist if you use bundled properties?

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/bundles.html

Andrew Sutton
andrew.n.sutton@gmail.com