I rationalized it as Kirk and Uhura as being something like grad students.
They are "cadet" because they are currently attending the Academy, but they have already experience (and probably a field commission) under their belt. In case of emergency, they can be drafted quickly into actual positions, and while technically still "student" they outrank officers with a junior commission (something like a bachelor's degree) like Chekov and Sulu.
McCoy is already an experienced medical doctor, so he get his commission as Lt. Commander. Since he's not in the command track, it's not really a problem.
Spock is probably a commissioned officer with some teaching duties, hence the grey uniform (instructor) while in the Academy.
Not perfect, but I like it,