After stripping all characters except '+' and digits from your input, this should do it:
^\+[1-9]{1}[0-9]{3,14}$
If you want to be more exact with the country codes see this question on List of phone number country codes
However, I would try to be not too strict with my validation. Users get very frustrated if they are told their valid numbers are not acceptable.