Gracias, ya había leído en php.net y algunos otros sitios el funcionamiento de preg_match, pero en el link que me otorgas esta mas que bien resumido y explicado, creo que lo guardare entre favoritos.
De casualidad note que antes buscaba un / en la regular, y ahora como el / para preg_match es un delimitador, me faltaba escapearlo para que funcione correctamente
Modifique esta linea y todo funciono de maravilla.
Código PHP:
'/(^((0[1-9]|1[0-2])\/[1-2][0-9]{3})$)|^0{0,1}$/'
Saludos