When I load it back into Perl using 'retrieve' it takes > 5 minutes.

That is very slow.

Using a a 32-bit perl, nstoring a 40e6 (numeric) element array took 12 seconds and produces a 200MB file:

C:\test>\perl32\bin\perl.exe \perl32\bin\p1.pl
use Storable qw[ nstore retrieve ];;

$#a = 40e6; $a[ $_ ] = $_ for 0..40e6-1;;

$t=time; nstore( \@a, '/test/junk.sto' ); print time()-$t;;
12.3673732280731
Terminating on signal SIGINT(2)

C:\test>dir junk.sto
16/05/2012  12:22       199,999,628 junk.sto
[download]

Retrieving it took 12 seconds and used 1.1GB peak:

C:\test>\perl32\bin\perl.exe \perl32\bin\p1.pl

use Storable qw[ retrieve ];;

$t=time; $a = retrieve( '/test/junk.sto' ); print time()-$t;;
12.2560520172119
[download]

A couple of possibilities:

Is the disk where you are storing it local? Heavily used? On its last legs?

Is loading the data (briefly requiring 1.1GB) moving you into swapping?