Es posible hacerlo sin utilizar una expresión regular.
import time
def isValidTime(data):
try:
time.strptime(data, "%H:%M")
return True
except ValueError:
return False
Quedando en tú código algo así:
if not isValidTime(date1) and isValidTime(date2):
print "Datos o formato incorrecto, deberia ser hh:mm \n"
Saludos.