Hover color smaller than menu height

I wanted the page menu height to be more than the standard, so I used padding to increase it, through a trick I found here on the forum. However, now when I set a different hover color, the area that changes color is the same height as the menu would be without the padding. I tried adding the padding to the hover element itself (or whatever it's called), and decreasing margins, but that doesn't work. Colored border big enough to fill up the difference doesn't work either.

Any suggestions?

Screenshot: I'm using the juggledad's color menu cheat sheet, (although I've been fiddling with it so the colors aren't standard anymore) and you can see what I mean.