Well it seems like you've gotten some good replies and some good analysis. So i wont add to that. What i will try to do however is help you break your mental block. (And OO fanatics and the like should take a deep breath when reading this. I intend to paint with broad strokes...)
In simplest terms OO is about strongly binding a set of information and a set of methods of manipulating that information into a single entity, essentially abstracting it all away into a black box that knows how to do something useful when properly prodded.
Now at this level OO is mostly useful for "sweeping the crumbs under the carpet". Lets say we are writing something that does something useful. Whatever :-). Along the way we decide that we want the output to be printed out in a certain way, perhaps wrapped adn maybe indented or something. And to keep track of the output we need a lot of "utility variables". You know things like the left position, and the right position, length on the current line, da de da... So after a while all this utility stuff becomes a pain. It clutters up your real code, its anoying to maintain etc. Putting as much as possible into subroutines helps, but if theres a lot of variables involved it alone wont help much. So sometimes its easiest just to grab all those variables, and the subs and turn them into a class. It knows how to create and initialize itself, it knows how to do whatever it is that its supposed to, all transparently from the point of view of the real program that you were writing. So now you have two advantages, first off if you ever need to have a pretty printer there is one available, in a box, for you to use. Second, if you decide, perhaps because you're now using it more places than one and you need extra functionality or efficiency, to completely rewrite the class all your other code will benfit, without having to be changed at all. (Assuming you maintain interface compatibility.) Eventually you might even upload it to CPAN. You never know.
Theres a lot more to OO than this. Some of the ideas get pretty deep and im not the one to tell you about them, but the above is at least a simple way that you can benefit from OO more or less imediately. Use it to conceptually group related code and variables into single objects that are then asked to do their thing.
A last word, people like merlyn and others have taken the time to write a number of excellent tutorials and documents on OO (the perl way :-) that are distributed with every perl (afaik, definately the AS ones) they are: perlboot perltoot perltootc perlobj perltie perlbot. And they probably should be read more or less in that order.