Well, you shouldn't trust any ADC you haven't calibrated and tested yourself. For 3 or 4 bits of precision, I bet it's pretty close to within 1 LSB. Though you don't know until you test it.
As far as the error-rate... I bet that could be fixed if you worked at it long enough, but losing .05% of the data stream is acceptable for some applications, like some basic audio work and as a basic oscilloscope.
Why is an ADC inherently less reliable at higher speeds? Also, robotbeat, I've never heard of someone calibrating an ADC on an AVR... I think if you get to a point where that much precision is important, you should probably use a discrete, dedicated ADC.
Because there are various types of ADC circuitry, and the one used in the avr chips is a sample and hold one, which have a cap that must be charged, then the time that it takes to discharge the cap is the analogic to digital value, so if you really want to sample very fast you need a lot of current so the cap will have the same voltage of your intended sample source, so if you cant provided an high-current sample you will have a reduced charge in the cap and thus reducing your adc resolution.