RobDrizzle:
I guess I'm kinda confused about the F macro. I'm already sticking the static strings in progmem... Aren't I?
Nope, not at all. Every Serial.print (or println) line needs to have the F macro explicitly used.
Looks like if you follow Coding Badly's advice you'll find your 500 bytes.
See http://arduino.cc/en/Main/ReleaseNotes for more info. Oh yeah, make sure you add the line
#include <avr/pgmspace.h>
Before you try to use the macro.
Hope this helps,
Brad