Catalyst is much more advanced down the development path than Maypole, but personally, I prefer CGI::Appplication because it's easier to learn, but the sheer volume of plugins being added in the last few months gives you a level of functionality on a par with Catalyst.
Catalyst has a steep learning curve IMHO, which is not helped by the documentation which seems a bit unstructured to me, but which obviously is sufficient for all those Catalyst programmers out there ... so I guess that it's personal taste.
A comparison between CGI::Application and Catalyst can be found here