First of all, you need to make sure you are entering your cell phone number in the international format:
+(country code)(city or carrier code)(your number)
Let's say you live in the USA and your cell phone number is 555-123-4567, then you need to enter +15551234567.
As of February 2017, Telegram supports VoIP numbers again, so you can now register with virtual numbers such as numbers issued by Google Voice. If you have a real SIM card phone number and it's not a virtual number (VoIP), contact firstname.lastname@example.org and provide the following details to them:
Brazil: Oi, formerly known as Telemar, is the largest telecommunications company in Brazil and South America.
They offer their customers a website where they can configure their account, e.g. blocking SMS from short numbers. It's important to disable the setting, in case you do not get any verification/login SMS. Login to http://minha.oi.com.br and disable "Recepção de Sons Imagens e Bate papo".