Everything you mentioned works correctly when I'm not using the PROGMEM directive and the pgm_read_byte function (just a plain array).
In other words, everything is fine (work as expected) until I move to the PROGMEM.
EDIT: I think I understand what's going on. I'm using pgm_read_byte(font4x6[x]) which is wrong. Changing to pgm_read_byte(font4x6 + x) works. Ahh.