It seems this is a growing problem lately.
I have an idea that this is possibly due to sketch size. When I load smaller sketches, and comment out several lines from my sketch, the program will successfully upload. The magic size seems to be about 28,636 bytes, give or take a few. 28,710 bytes is slightly too big. Unfortunately, this means I need to omit about 5 lines of code, lines which are necessary. I've trimmed and streamlined everywhere possible at this point, including the complete removal of one of my sensors.
The IDE states we have a 32,356 byte maximum for our sketches, but obviously some of this is eaten by the 2,048 bytes of bootloader data. IMO, that should be reflected in the maximum allowed sketch size. The IDE should report 30,308 bytes maximum, although that's still obviously not true - I seem to be losing around 4k.
So, I'm left with either redesigning my project to utilize an Arduino MEGA (which will screw with my shield pinouts and physical construction), use a second Arduino UNO to govern my sensors (which will raise costs and power consumption), or write a program which will parse the raw data on my workstation (which will waste time and cost money).
It seems like 32k is a lot of space to write a program to utilize the Arduino to its fullest. It isn't. I realize this isn't the fault of the Arduino makers and rather a drawback of the ATMEGA328P chip itself, but it still kinda sucks.
EDIT: I should clarify that I have replicated this problem on twelve Arduino UNO boards, both R2 and R3 using both Arduino 1.0 and 1.0.1.
If you need all that last bit of space, get an ISP and remove the bootloader.
Remember that RAM is organized in words, and EEPROM is organized in pages. This means that not everything will round to a single byte, and why you seem to be over-allocated.