Well, PHP’s rand() takes an inclusive range, so your original code was leaving off the colors from 16,700,001 to 16,777,215, the latter being the maximum value of an unsigned 24-bit integer (2^24 - 1). That’s a total of 77,215 colors omitted.
I think one reason you’re getting weird color results is because some of your color specifications are invalid. Numeric color values in HTML/CSS can only be 3- or 6-digit hex strings, e.g., #f042d1 or #a22. PHP’s dechex() does not do any padding; you get the shortest string containing a hexadecimal representation of the integer passed as the argument. So if your randomizer picks, say, 874161, the result of dechex will be D56B1, which is five digits long and not a valid HTML/CSS color value. I think invalid color values are ignored, so you’ll just get whatever color the element would have had without the style specification.
Additionally, the 3-digit color values will be interpreted differently than the 6-digit values. #fff will be white, for example, while #100000, a much higher number than #fff, will be a very dark red. To ensure that you’re actually getting a random sampling from the whole 24-bit color space, with 0 being black and 16,777,215 being white, you’ll need to pad the results of dechex() to 6 digits by prepending zeroes.