Just to clarify, REM is not the deepest state of sleep, it's actually Non REM sleep otherwise known as Slow Wave sleep that is the deepest state of sleep.
I just took a class that explained why you experience REM atonia. It turns out that there are a group of nuclei within the ponswhich release GABA called the Nucleus Reticularis Pontis Oralis. GABA cells in pons inhibit wake promotingnoradrenergic, seratonergic projections, but activate cholinergic neurons. Descendingcholinergic projections lead to muscle paralysis.
So, if you wake up, and can't move, chances are the enzymes and that are responsible for the breakdown of acetocholine or the reuptake of Ach are not doing their job and so you they are still innervating your muscles, which thereby paralyzes you.