Isolation for microcontroller that is off
My first reaction is that trying to externally turn off the micro is the wrong way to go about this.  Perhaps you are using the wrong micro, but there are micros that take very little power when in full sleep mode.  Take a look at some of the "nanoWatt" (marketing term) PICs and MSP430s.  The latest PICs are basically down to a tiny amount of leakage current in sleep, less than 1uA for some.

How low a current do you need?  What does the rest of the circuit draw.  What is the CPLD current when it's not switching?  It's hard to give a good answer without some real numbers.

Saying that something is a "huge issue" is no spec at all.  For example, if you are trying to run something as long as possbile on a CR2032 battery, then 1uA sleep current is fine since the effective self-discharge current is more than that.  If you want 3 years from a single AA battery, then even more would be acceptable.

EDIT: Something else I should have added.  If you really are going to switch power to the micro (I still think that's a bad idea, get the right micro instead), you probably need to switch the ground instead of the power.  You say there are IIC and UART lines connected to the micro.  IIC has passive pullups, so these will either draw current or power up the micro thru the protection diodes if you try to switch off the power instead of the ground.  Logic level UART signals idle high, so there could be a similar issue there too.

In any case, you can apparently redesign the board, so I don't understand how you're stuck on that particular micro, whatever it is.  If power is really such a "huge issue", then everything else should be on the table.