my $message = uc(<>);
$message =~ s/[^A-Z0-9]//gi;                # remove punct, etc
$message =~ s/j/i/gi;
$message =~ s/q/O/gi;                      # replace [Qq] with [Oo]
$message =~ s/\s+//g;                      # remove spaces
[download]

• You UPPER case the contents of $message at the beginning so the use of the /i option seems strange.    Why not just use upper case letters in the pattern?
• Your comment says "replace [Qq] with [Oo]" but that is not what your code is doing.
• Your last substitution attempts to remove "spaces" which were already removed by your first substitution
• And your code would be more efficient using transliteration instead of substitution:

my $message = uc <>;
$message =~ tr/A-Z0-9//cd;        # remove punct, etc
$message =~ tr/JQ/IO/;
[download]

Update:

my @range = ("Q","V","X","Y","Z",);

...

        my $i = int(rand(4));
        my $letter = $range[$i];
[download]

Your @range array contains five elements but you are only accessing the first four of them.

That is usually written as:

my @range = ("Q","V","X","Y","Z",);

...

        my $letter = $range[ rand @range ];
[download]