For starters, the syntax would be

# 'categories' entry is 'GNOME;Games;Action'
push @{ $out{GNOME}{Games}{Action} }, $val;
# 'GNOME;Games;Action;FPS'
push @{ $out{GNOME}{Games}{Action}{FPS} }, $val;
# ...and so on.
[download]

But you got another problem. You're trying to get an array reference and a hash reference to coexist in the same variable.

$out{GNOME}{Games}{Action}[0] = $val;
$out{GNOME}{Games}{Action}{FPS}[0] = $val;
                          ^
                          |
                         XXX
[download]

Perhaps you could use the items of a specific category could be placed into a special* key. Say "_".

$out{GNOME}{Games}{Action}{_}[0] = $val;
$out{GNOME}{Games}{Action}{FPS}{_}[0] = $val;
                          ^
                          |
                          Ok
[download]

* — Special to you, not to Perl.