Ok. I figured it out and this is the thing.
If you have not bought your domain from GoDaddy (or transferred it to them), they allow you reroute your domain to them by pointing to their NS or specifying their A Record - but they do not allow you to set MX records, or CName records from their end.
This is only for their paying customers.
However, if you reroute to them via changing the NS records, they automatically setup the MX records for you pointing to their own mail servers.
So this is what I ended up doing. I pointed my NS to theirs and setup email on their mail server (they give you some email space free if you are hosting your website with them).
I am using Godaddy mail servers for this website - but its okay. Its doing the job for now.