How can I get a linear relationship between a voltage divider and an ADC?
You state that at 128, you measure about 500mV. This means at full scale (256) you measure about 1V.

According to the datasheet (14.12) with:

// Set ADC reference to AVCC
ADMUX  |= (1 &lt;&lt; REFS0);


You actually do the following:


  This bit selects the voltage reference for the ADC, as shown in Table 14-2. If this bit is changed during a conversion, the change will not go in effect until this conversion is complete (ADIF in ADCSRA is set).


Table 14-2.

Voltage Reference Selections for ADC
REFS0   Voltage Reference Selection
0       VCC used as analog reference.
1       Internal Voltage Reference.


Paragraph 14.3 states:


  The ADC converts an analog input voltage to a 10-bit digital value through successive approximation. The minimum value represents GND and the maximum value represents the voltage on VCC or an internal 1.1V reference voltage.


So in conclusion, you are setting the ADC reference voltage to 1.1V and with that knowledge your findings are pretty accurate.