The padding looks fine in IE6 and IE7. Did you do a hard refresh to make sure you re-loaded the CSS file?
You can also try adding a query string to your link to your css file.
ie: <link href="css/style.css?random" rel="stylesheet" type="text/css" />
Let me know,