The problem is all relating to your hard coding the length of your arrays into the rand() calls. Never count your lists by hand! Never count anything that relies on parts of your code; if it relies on the code, make it dynamic. Try this instead:

print "gimme a seed: ";
$s = <STDIN>;
srand ($s ^ time);
@chars = qw(b c d f g h j k l m n p r s t v w x z);
@vowels = qw(a e i o u y);

for($i = 1; $i <= 4; $i++) {
    print $chars[int(rand(@chars))], $vowels[int(rand(@vowels))];
}
[download]

Notice that all i did was replace the hard coded values with the arrays, which will be correctly used by rand.
Yay! for context!