Turns out I forgot to set the time zone on my slicehost instance after we moved. If you ever need to do that on slicehost (or other linux boxes) then this should work fine:
dpkg-reconfigure tzdata
More information about formatting options