I don't see why you made this module object oriented - you're not making any use of $self. Also, you're reading DATA in your new() method - why? The second and subsequent instantiation of an "object" in your class will not have anything to initialize. Pull that while loop out of the method and get rid of new (as well as $self in the other functions). Of course the function names are somewhat unfortunately named for those who'd want to import them; maybe prefix them with us_ or some such.
As far as the name is concerned I'd definitely go with Geography::US::Census::Regions. Locale is the wrong namespace for this module. A module's "innermost" name portion should express what that module deals with; here, that is regions. It deals with those according to the census, hence Census::Regions. Regions::Census would mean it deals with the census according to the regions, which makes no sense.
Makeshifts last the longest.