In order to re-associate you device to a different Gmail address you will have to do a Factory Reset of the phone and go through the setup with your new Gmail address.
This will completely reset your phone so proceed with caution! You will have to re-download all your apps. Be sure you backup your contacts first and also copy off any pictures/movies/docs that you may want to save to your PC for safety.
Even if your contacts are synced to Gmail, you will want to back them up to your SD card or PC because they will not be in your new Gmail account unless you already put them there.
Also, any apps you purchased in the Play store will still be tied to your old account.
I know it's kind of a bummer, but it's the only way to completely link to a different Gmail address.