Hmm I'm having a hard time visualizing your counter example, I'll try to think of it some more. An important detail I left out though is that in my problem sets edges do not cross, which I suppose simplifies the entire problem a lot :-)
I think this is roughly the counterexample the person above was suggesting.
It's an edge case that should be handled, but does not prevent the general algo from working.
However, indeed it remains true that it does not find all loops, only the smallest set of loops that cover all edges.