Unfortunately, no luck... And I didn't have this problem with adjacency_list (sorry for not saying this explicitly before!) and the same compiler (g++ v4.3.2). I guess that made me wonder if maybe this constructor does not exist? Or maybe I need to #include something more besides just "adjacency_matrix.hpp"?
Hmmmm, I hope this is not too much to ask, but can you or someone else check if the sample code I posted before compiles (with the offending line uncommented)? I should compile as-is... Just to check if I'm going nuts... :-) Here it is again below [with the line commented out, so this should compile].
After looking, that constructor may not exist in Boost 1.39. It exists in trunk, but it seems to be causing problems (can't find add_edge).
Your best bet is to construct the matrix over n vertices and then manually populate the graph with edges.