Don't forget the mode. The threat of physical punnishment should be secondary here. Your players have crossed the borders of reality and have entered a place older than the creation of their world (Hey. It sounds cool

). This place exsist on the brink of insanity. Here they feel small and insignificant. The queen they are facing is only a small part of a much larger much more terrifying truth. They realize that now.
Here exist smells they have never before smelled, shadows that don't act normally. Sounds that seem to be comming from the walls or are they in their heads? Could it be that they only truely exist here because of their souls. And that their minds have difficulties comprehending this?
It is a tale of what have been and a forwarning of what will become again. That they now 'know' is true. If they find a window the horison will seem endless. Or is it just still because they cannot comprehend what they see?
Nothing seems certain anymore. Can they still trust their skills here? Can they really do this? This was certainly not what they had expected. They start being afraid (It's the nature of the place

).
Maybe the'll encounter living furnitures that have been made from mortals using fleshshaping magic. Still with their minds and memories intact... More or less.
Try and use advanced HD or character levels on some of the demons they encounter. That will help them get the feeling of being in truble if they have encountered that type of demon before.
I think it have been mentioned by others but if you stick with the idea about disorted physical distance you could try these:
-What about hallways that seems endless (You keep walking) even though you can see the door up ahead (The trick will be that you have to walk backwards. Your senses fool your here remember?

- ).
-A door in a hallway that leed into another hallway that is infact the same hallway just half a mile up.
Maybe any "Good" related spells will have a -2 on their effective spell level.
Have them encounter a section of rooms where the men and/or women of their fantasies exist. Let them realise that these men/women are endeed good willed. They only wan't the heroes to stay for a moment. The may explain that the demon queen have taken then from the realm of dreams to use against the heroes but that they found them before anything happened. This will be their only chance to be together for real. And they beg the heroes to accept because that is the only purpose of their existence. They are after all the creation of the heroes. (If the heroes chose to stay with the dreamspirits they will slowly starve to death. What will seem like 10 min. Will actually be a day. The heroes will not know this before they try to leave the rooms- Or maybe they will infact be demons playing with their newfound toys)