Dai il float all'elemento li e nel contempo applica la proprietà display:inline. Probabilmente il problema deriva anche dal fatto che hai impostato un padding unico per tutti i lati. IE ha notoriamente problemi con il padding.