What is the difference Memory Leak and a Zombie?
"Zombies" in Objective-C parlance are the opposite of leaks. A leak is a bit of allocated memory that you no longer have any references to, so you can't free it. A zombie is an object that has been deallocated, but references to it still exist and messages are still being sent to it (which can lead to all sorts of unpredictable behavior).
There are several possibilities and it's hard to know what's going on without seeing code. The "message passed to a deallocated instance" error means that you have a pointer that points to where an object had been, but has since been deallocated. This can and does still happen with ARC. It can happen because you have some non-ARC code (or perhaps Core Foundation stuff) interacting with ARC code and things are going awry at the hand-offs. It can also happen because while ARC picks the correct points in time to release objects nearly every single time, it's not perfect (usually there are ways to work around these instances).