Add the custom domains addon and add the domain your going to use, eg www.mywebsite.example to your application
Go to your domain registrar control panel and set www.mywebsite.example to be a CNAME entry to yourapp.herokuapp.com assuming you are using the CEDAR stack.
There is a third step if you want to use a naked domain, eg mywebsite.example when you would have to add the IP addresses of the Heroku load balancers to your DNS for mywebsite.example
At a guess you've missed out the first step perhaps?
Following the announcement of Bamboo's EOL proxy.heroku.com being retired (September 2014) for Bamboo applications so these should also now use the yourapp.herokuapp.com mapping now as well.
You can't use the naked domain of your-domain.com if it is not redirected to the www.your-domain.com. Heroku use the www.yourdomain.com which act here as a subdomain. So when you follow the default instruction to use your-domain.com then you will need to assign both of them.
We can actually assign only the naked domain without the www.your-domain.com. Use only your-domain.com when the domain's dns provider (NameServers) support ALIAS or ANAME for the @ Record to example.herokuapp.com without CNAME www.your-domain.com to it.
It will let you to point www.your-domain.com to other hosting separately (independent).
Yes, many changes at Heroku. If you're using a Heroku dyno for your webserver, you have to find way to alias from one DNS name to another DNS name (since each Heroku DNS endpoint may resolve to many IP addrs to dynamically adjust to request loads).
A CNAME record is for aliasing www.example.com -> www.example.com.herokudns.com.
You can't use CNAME for a naked domain (@), i.e. example.com (unless you find a name server that can do CNAME Flattening - which is what I did).
But really the easiest solution, that can pretty much be taken care of all in your GoDaddy account, is to create a CNAME record that does this: www.example.com -> www.example.com.herokudns.com.
And then create a permanent 301 redirect from example.com to www.example.com.
This requires only one heroku custom domain name configured in your heroku app settings: www.example.com.herokudns.com. @Jonathan Roy talks about this (above) but provides a bad link.
Scroll down to the bottom you will see Manage DNS.
It will navigate you to DNS settings then add the entry similar to mentioned below and delete all other CNAME records. Here the value of points is your DNS target that you got in the 4th Step.
Then after some time your site should be mapped to the Heroku app URL.