obviously straight lines on (some) projections are very wonky on a sphere (or geoid), as would be shapes built on those lines. That was not really the question though, the question was that if you have shapes defined by points connected with shortest great circle paths then when (and how) would that fail?
Sibling comment already raised the good point that great circles do not work that well on spheroids and other more complex models of Earth, but I got the impression that it was not what apendleton was referring to
Assuming the world is a sphere (which we know it isn't, but it's not disastrously wrong for these purposes), that gives you something that looks like this:
http://gc.kls2.com/cgi-bin/gc?PATH=NYC-TYO-LON-NYC
The slightly-curved lines represent the shortest distance between those points; the great circle routes.
Now take your typical world map (probably a Mercator projection) and draw the same triangle on it using straight lines along the shortest distances on the map.
Notice that the triangle on the world map includes within its area a significant chunk of Central Asia and absolutely none of Greenland.
Imagine how unsuccessful you would be trying to intersect the world-map triangle with another polygon; it would be completely meaningless.