How to write a validation formula that doesn't allow letters?

I usually research and tweak examples I find to fit my needs, but in this case I'm struggling to understand how the REGEX function can be used to complete the task of disallowing any values outside of numbers, parentheses or hyphens in a phone number field.

I want users to be able to use parentheses or hyphens or "+" but not be required to. I also want users to enter numbers, but not specific amount of digits. I just don't want letters to be allowed.

Here's what I have so far: 

AND( NOT(ISBLANK(Phone)), (REGEX( Phone ,"^[0-9 + ( ) -]*$")) )

But it's throwing up errors when I enter "1234567" or "123-4567". What am I doing wrong? 

#Validation Rule #Formulas