Most likely, you're failing to retain some object somewhere along the way. When an object gets released and then the memory is re-used for something else, you'll get all sorts of bad behavior, including crashes, or mysterious "disappearance" of other objects.
One thing you can try is putting breakpoints into the -dealloc method of your custom classes. Then you can see where they're getting deallocated from. Most likely though, this will end up being when the AutoreleasePool gets drained, which won't tell you much.
Alternatively, look into using some of the memory debugging tools built into Cocoa.
That document is for Mac OS X, but I think most all of this will work in the iPhone simulator, at least. I know that your bug "doesn't happen" in the simulator, but that really only means that the symptoms are different, and you're not noticing them.