Well, weather it's illegal or not really depends on where you are. There's no law in Bolivia for example that prevents it...
But seriously, unless you want to (try and) deceive your carrier there is no valid reason for a consumer to need to change the IMEI.
What problems are you experiencing with your new phone that you want to address?
[Nexus One], [Optimus 2x > /dev/null], [Galaxy Nexus], [Transformer Prime], [Nexus 5]