Hi arcademissile and thanks for your input.
I did the same test on an unARCed project with all the correct calls to [super dealloc] etc, and got the exact same behavior.
However, after closer inspection, it seems I don't have leaks after all but was just not interpreting the results correctly.
So I have the program on an initial state and take a heapshot. I then press the ui button that makes the scene to be replaced and then reloaded. I get back to the initial state and take another heapshot and notice that the heap had a growth of around 20kb or so. When i press the ui button again the previous heapshot goes back to zero bytes. After doing this a few time, the previous heapshot goes always back to zero bytes.
Because in cocos2d everytime you replace a scene everything attached to that scene is deallocated, and when you come back to it, everything is allocated again. So I think there will always be an heap growth because that growth is the size of the Scene with that layer as a child. Am I correct?
Also i noticed that everytime I did this, the #Living column in the statistics was not increasing, which is a good sign, right?