Buenas,
lo primero que tendrias que hacer es poner el codigo html correctamente, el div no sería necesario pero los <li></li> deben ir dentro de un elemento <ul></ul> que englobe a todos ellos y dentro de los<li></li> iría el enlace. Al elemento al que le debes aplicar la propiedad float es a los <li> y el padding deberia funcionar puesto que es un elemento en bloque. Validar el codigo tanto html como css te facilitará el trabajo y usar alguna herramienta como firebug que te ayude a detectar errores también