Yo como interfaz gráfica no veo lógico que el padding dependa del ancho de la pantalla. Es un poco extraño. Además, como los enlaces no tienen un ancho fijo definido no existe ningún cálculo para que siempre se ajusten al 100% del ancho junto al padding.
Yo haría más bien alguna cosa así:
Código CSS:
Ver originalnav#main_nav a {
width: 20%;
padding: 30px;
box-sizing: border-box;
}