It might be useful to separate out the concepts of encapsulation and data-hiding.
A package global variable is encapsulated within it's package (declaring $Foo::fribble does not interfere with $Bar::fribble), but it's not hidden (you can access $Foo::fribble from the Bar package by explicitly stating the package name).
Contrast this with a lexical variable which is both encapsulated within its scope and hidden from other code (ignoring closures and PadWalker :-)
Language support for the encapsulation of class state and behaviour is, for me, the big lack in perl5 OO.
Using the default perl OO style of key/value pairs in a hashref to represent an objects state gives you a single namespace for attributes across all the classes that the object belongs to. The same applies to methods. Using the normal $self->method style means you have a single namespace for methods across all the classes the object belongs to. They are not encapsulated.
Imagine having to develop functional/procedural perl modules without packages. You would have to make sure that every module used different subroutine names and different global variables. While the situation isn't so desperate in the perl5 OO world, because deep inheritence hierarchies are rare, it can still be a problem.
In perl5 you cannot encapsulate the implementation details of your class from its public interface easily - its complex (e.g. lexical closures), non-obvious (e.g. inside out objects) and can involve a lot of developer overhead (e.g. prefixing all attributes with the package name and remembering to call all private methods as subroutines).
This is why I'm looking forward to things like submethods in perl6 ;-)