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.