Amigo, a algum tempo atrás utilizei o seguinte regex para fazer sua validação:
(\(?\d{2}\)?) ?9?\d{4}-?\d{4}
Adicionei o mesmo à comunidade do regexr: http://regexr.com/3emuj
Espero ter ajudado.
P.S: Você pode inserir esse regex no atributo pattern do input referente ao telefone para fazer uma validação client-side.