Strictly speaking, ut's even more complex than that mate.
A connection speed is (strictly speaking) measured in BAUD per second. A Baud is a change in state from a zero bit to a one bit, or vice versa. If you were only sending hex A or hex 5 (i.e. 1010 or 0101) then Baud speed could also be measured in bits per second.
Most people, however, nowadays measure connection speed in bits per second. There are 8 bits in a byte, but if you are using a parity bit too, then there are 9 bits in a byte. This is why, as you said, when you have a speed of (say) 512Kb Kilo BITS) per second then you may see it reported as 64KB (kilo BYTES). Generally, a small "b" refers to bits and a capital "B" refers to BYTES.
(yeah I know)