One solution, though it looks ugly, is to call Program::Plist::Pl::Pattern::->new(). This disambiguates between the package and any possible function of the same name as the package.
Comment on Re^2: Moose, @ISA and method resolution
This is quite true, and another reason why MooseX::Types won't get into core Moose. In my opinion it is unacceptable to put the burden of change on the user like this.