top padding or margin not working

I have the following for a horizontal navigation and it seems like I can't
give 
my links top and bottom padding or margin. Why could that be?

 I have this and the horizontal spacing seems to work, but not the
vertical one?
 #mainnav a {
     text-decoration: none;
     margin: 15px 12px;
 }

 Thanks a lot for any help with this. 


 here is the whole css: 

 #mainnav {
 	font-size: 12px;
 	font-weight:bold;
 	text-align: center;
 	background:#bf0e20 url(../images/general/nav_bg.jpg) repeat-x;
 }
 #mainnav ul {
 	
 }

 #mainnav li {
 	display: inline;
 	list-style: none;
 }

 #mainnav a {
     text-decoration: none;
     margin: 15px 12px;
 }
 	
 #mainnav a:link, #mainnav a:visited {
 	color: #fff;
 }

 #mainnav a:hover, #mainnav a:active,
 #uberlink a:link, #uberlink a:visited,
 #uberlink a:hover, #uberlink a:active {
 	/*background-image:url(../img/general/btn_bg_over.gif);*/
 	background-repeat: no-repeat;
 	color: #1070ca;
 }