I don't see any reason why that wouldn't work, unless there's an issue somewhere else in the code. Both the tiles and their collisions should be removed if the tiles were created via code. Tiles that are placed in the scene editor can be removed, but the collision boxes persist. If you turn on debug draw, you can see what's really happening--the scene editor merges collision boxes in an effort to reduce Box2D's CPU usage. The drawback is that these tile collision boxes are permanent.