Is better if you recreate the product. The attribute set defines product parameters (all the attributes) and you can't really modify all those relations. Even if you change the attribute set id inside the database, you will have to remove garbage entries of previous attribute set. There are some third party extensions that allow you to convert one attribute set to another, but even with them it won't be a clean process. Usually is easier (and cheaper) just to create your product again.
Since by default it is not possible in Magento, I can recommend you extension that allows to change attribute set called eMagicOne Store Manager. It allows to do it in the safe way as it changes attribute set and unassigns attributes and values of previous attribute set. This way you will not have mess with attributes and database. It is paid, though there is 14-day fully-functional version, so in case you need to do this once or a few times, you can cope without any fees at all. Here is the video of how i works in action - https://www.youtube.com/watch?v=766pIaaC1ds