As lima1 pointed out this behaviour has been deliberately changed as of the perl 5.8.*, I get this with 5.8.1:
[jonathan@orpheus jonathan]$ perl foo.pl
potatos diced
pepper fresh
salt shaken
paprika spicy
onions diced
[jonathan@orpheus jonathan]$ perl foo.pl
pepper fresh
potatos diced
onions diced
paprika spicy
salt shaken
[jonathan@orpheus jonathan]$ perl foo.pl
salt shaken
paprika spicy
onions diced
potatos diced
pepper fresh
but yes it would be a mistake to rely on an any hash ordering behaviour in a programme.
/J\