They are not the same.They are two types of flash memory cards.Most devices work with both of the though.
You can read something about theirs spec here: http://www.davespda.com/hardware/expansion/cfmmcsd.htm
What about the p800 case,it seems that it does not support 256 MB MMC's but it does support the 128 MB ones.
That wouldn't suprise me that much. Manufactures can set limits on the size of card supported. It is often seen with MP3 players. Obviously the more the better for the long term.
__________________
After waiting for the Nokia 3650 I eventually got myself this instead!