Example:

| | = Enemy Space Enemy
| = Space MyUnit Space

I can't pass between the two units. And according to the rules I shouldn't be able to.

But the AI pass's my units all the time!!!! I mean WTF! Why can the computer pass my units by and I can't?

Do others have this problem as well. Or is there something I am missing?

Stealth units are:
Slaver
Abolitionist
Spy/Cyber Ninja
Clerics/Televangelists.

Also, Diplomats, while not stealth units (AFAIK), ignore ZOC because they are, well, diplomats. You can only see enemy stealth units with your own stealth units.

Now, if the enemy moves a stealth unit into a gap between your units, he can then move normal troops into the space because he already has a unit in that tile. However, if they programmed that into the AI, I'd be surprised. And then, it may not work that way in CtP2 (it did in Civ2 and SMAC).