Mi sono dimenticato di farti aggiungere
float: left;
sia alla formattazione di <a> che a quella di <span>

In alternativa prova a togliere il display: block da <a>. non si sistemano piu` i kB uno sotto l'altro, ma si evita di farli andare a capo.
In tal caso puoi anche togliere il display dal[*]: anche questo peggiora un po', ma ti aiuta a sistemare i margini e padding.


Altra prova: prova a sostituire il margin con il padding per lo spazio per l'icona: alcuni brwoser lo preferiscono.