Assuming you followed the instructions here:
You should’ve been able to do exactly that – – remove the device from one room’s list of things and add it to a different room’s list.
(Note that this is very different from deleting a device from the network altogether, and should not require a reset of the device itself–you’re just moving it from one group to another. And you shouldn’t have to have the hub re-find it – – you would just find it yourself in your existing things list and assign it to a different room.
That is, you’re not deleting the device from the network: your editing the list for single room to delete it from that list.)
Since you’re now getting the error message, it sounds like there may be some database corruption on your account.
You could try putting the device into a new group by using the IDE through the web interface if you’re comfortable with that.
But if you haven’t used the IDE before, I would just contact email@example.com and let them help you.
If you have used the IDE before, try just assigning The device to a room and see if that fixes things.
Starting back in March or April, SmartThings began to be very unhappy if there were devices that were not assigned to rooms. That was a change, but I’m not sure exactly what caused it. It wasn’t an announced change.
It may be that you’ve uncovered a glitch that will affect other people as well. So I would definitely report it in any case, even if you’re able to fix it yourself.
Or it may be that by accident you did force delete the device from the network, rather than just edit the room list. In that case, as @desertblade pointed out, you would have to reset the physical device in order to be able to re-add it to the network. But you still shouldn’t have gotten that error message. So you should still report it to support just so they can look into that.
Let us know what happens!