rand() uses (IIRC) the built-in rand() function on your platform. This is a pseudo-random number generator, not true random numbers. Perhaps the rand() function is not up to snuff on your OS.

BTW, random doesn't neccessarily mean no duplicates. The sequence 5 5 5 5 5 is just as likely as the sequence 3 2 4 1 5 or 1 2 3 4 5. It just doesn't look random to us humans, who are wired for pattern recognition.