This is another non sequitur. PAE increases the amount of physical memory that can be addressed by the processor, but that is unrelated to virtual address space. (Remember that PAE stands for Physical Address Extensions.)
PAE increases the physical address space (the address space that the CPU can use to access the memory chips on your computer) from 32 bits to 36 on a Pentium 2, for a theoretical maximum physical memory capacity of 64GB. However, the size of a pointer variable hasn't changed. It's still 32 bits (for a 32-bit processor), which means that the virtual address space is still 4GB.
With PAE enabled, the page table and page directory entries double in size (to accomodate the additional bits in the page frame), which significantly increases the amount of memory required for page tables and page directories (since each page table describes only half as much memory as it used to).
Notice that this has as a consequence that PAE and /3GB conflict with each other to some degree. If you turn on both PAE and /3GB, then the kernel will limit itself to 16GB of physical memory. That's because there isn't enough address space in the kernel to fit all the necessary memory bookkeeping into the 1GB of memory you told the kernel to squeeze itself into.
(On an AMD processor, the physical address space expands to 40 bits, for a theoretical maximum of 1TB. However, the memory manager uses only 37 of those bits, for an actual maximum of 128GB. Why? For the same reason that the kernel limits itself to 16GB in /3GB mode: Not enough address space. It's time to move to 64-bit processors...)