I have bought a domain from 123-reg.co.uk and have successfully pointed it to the IP Address of my Linode VPS so that going to the domain serves up the pages from the Apache server running on the VPS. The instructions I followed to do this are :

Now, I am trying to get the domain's mail handled by Google Apps for Business.

I have tried updating the MX records at Linode following this tutorial : http://library.linode.com/email/google-mail

And also followed the instructions to update the MX Records in 123-reg's control panel :

I am slightly confused now. Where should I be adding the MX records? In my domain registrar's control panel or in Linode's VPS? Both have options to update the MX records.