To be clear, the new company is in a completely different market and will not be competition. They want all the shares back and I guess I will need to get something written up from a lawyer soon. Thanks for the info!
You could give them your shares back, but don't do it for free. If you want to be nice then sell them back cheaply or trade them for something you want.
With proper legalese (read: talk to a lawyer to get a proper contract) you can trade your shares for the company agreeing that they will not sue you for trade secrets/ideas/code/etc.