I agree with Marshall (Re: Perl Best Practices - Loop Labels), although I'd clarify somewhat:

I generally avoid manifest nested loops that require jumping between levels by refactoring the code, often by putting the inner loop in a sub and using an early exit to bail. That has the advantage that it completely avoids "spaghetti" code and allows a descriptive name to be used for the sub. Identifiers, be they labels or sub names, can make understanding the intent of the code much easier without needing to introduce comments. Putting the inner loop code in a sub generally cleans up the outer loop wonderfully so the logic is easier to see. The result is code that is easier to grok and thus easier to write and maintain.

Having said that, there are no hard rules. Either approach may be more suitable in different situations. But, like Marshall, I don't remember when I might have used a loop label. Maybe never. I have a few workmates who use them as error exits from loops (in C++ as it happens), but very rarely (a hand full of times in a few tens of millions of lines of code).