I have tried pushing references to @odds etc. onto @parts before using part without success ...

AFAIU, the list of anonymous array references  part returns is entirely independent of anything that has gone before; you would, indeed, be on your own in getting them into a set of named arrays.

For my money, the two examples you give don't seem all that different in terms of effort needed to generate the final, named arrays. But of course, this is entirely a matter of individual programmer style and taste! I must admit I have never used  part except to become familiar with it.

The only situation in which I can see a problem developing is if you needed to distribute an input list into a vast number of 'parts'. In this case, I think I would still go with the AoA approach. (Of course, in such a case a purely hash-based approach would probably be even better!) Note that in the example below, the definition of the exact index (i.e., $_ + 7) of each 'part' does not matter, nor does the way they are used in the  part code block, so long as they are all unique and properly associated!

>perl -wMstrict -lE
"use List::MoreUtils qw(part);
 ;;
 BEGIN {
   my @parts = qw(EVENS ODDS FIVERS);
   eval qq{sub $parts[$_] () { $_ + 7 }} for 0 .. $#parts;
   }
 ;;
 my @parts =
   part { $_ % 5 == 0 ? FIVERS : $_ % 2 == 0 ? EVENS : ODDS }
   0 .. 20
   ;
 ;;
 say qq{'@{$parts[ODDS]}'};
 say qq{'@{$parts[FIVERS]}[1 .. 3]'};
 say qq{'@{$parts[EVENS]}'};
"
'1 3 7 9 11 13 17 19'
'5 10 15'
'2 4 6 8 12 14 16 18'
[download]

Update: What I had in mind for a 'purely hash-based' (actually, an HoA) approach:

>perl -wMstrict -lE
"BEGIN {
   eval qq{sub $_ () { $_ }} for qw(ODDS EVENS FIVERS);
   }
 ;;
 my %parts;
 for my $n (0 .. 20) {
   push
     @{ $parts{ $n % 5 == 0 ? FIVERS : $n % 2 == 0 ? EVENS : ODDS } },
     $n;
   }
 ;;
 say qq{'@{$parts{ODDS}}'};
 say qq{'@{$parts{FIVERS}}[1 .. 3]'};
 say qq{'@{$parts{EVENS}}'};
"
'1 3 7 9 11 13 17 19'
'5 10 15'
'2 4 6 8 12 14 16 18'
[download]