I tried to kill the wall of flesh a few hours ago and failed. I decided to build up a platform and try him again. Long story short, I drop the voodoo doll in the lava, the guide dies and...the boss doesn't spawn. I've tried saving and exiting twice now.
I say you have to wait a full Terraria day because when you die, you have to wait for the WoF to reach the other side of hell. You summoned another one right after killing one because you actually killed him and didn't die.
We ran into that problem yesterday, but my friend figured that it's because the guide didn't respawn into the world due to a lack of homes. I think a new NPC went into his house after the guide died, preventing his return. Remember that you have to make a human sacrifice to get the Wall of Flesh to appear, so be sure that the guide moves in before you throw your guide voodoo doll into the lava.
In terms of where to spawn, we made a hellevator from the middle of the map to right where the Underworld begins. It should work if u are near the middle of the Underworld.
I managed to fix the problem. I read on the main site that this is a known glitch. By simply deleting the steamapps folder and verifying my installation, the problem was solved. Hopefully if anyone else has this problem this solution may help them.