I think I was wrong about the case simply being "when the segment is parallel to one of the edges of the shape". I noticed that my little man could run along the falsely intersected ground quite happily until he got quite close to it, at which point TestSegment worked correctly again. Here is the original case where I noticed the problem:

Since the segment being parallel to the edge of the shape was what I noticed when stepping through the code, and changing it fixed the problem, I thought that was that. But later I found that when the character got near the shape, there was a point where the test worked ok. As you can see in the image below with little man ver.2 now sporting his new bevelled edge look and an extra 'leg', the leg segment on the right has correctly missed the shape, while the leg on the left has incorrectly intersected with it.

I can't figure out why this is, so considering it might be a harder thing to reproduce than I thought, here's the reproduction:
Code:
b2AABB worldAABB;
worldAABB.lowerBound.Set(-500.0f, -500.0f);
worldAABB.upperBound.Set(500.0f, 500.0f);
b2World world(worldAABB, b2Vec2(0.0f, -9.8f), true);
b2Body* pBody = world.CreateBody( &b2BodyDef() );
b2PolygonDef shapeDef;
shapeDef.vertexCount = 4;
shapeDef.vertices[0].Set( 47, 5.95f );
shapeDef.vertices[1].Set( 53, 5.95f );
shapeDef.vertices[2].Set( 53, 6.05f );
shapeDef.vertices[3].Set( 47, 6.05f );
b2Shape* shape = pBody->CreateShape( &shapeDef );
b2Segment segment;
segment.p1.Set( 0, 7 );
segment.p2.Set( 0, 5 );
float lambda;
b2Vec2 normal;
bool shouldBeFalse = shape->TestSegment( pBody->GetXForm(), &lambda, &normal, segment, 1 );