Being a total roguehead myself I have been particularly interested in the recent blogs discussing procedural generation. Coincidentally I recently implemented a BSP dungeon generator for my latest project. Initially it gave me a lot of trouble despite it's theoretical simplicity, but with persistence I was able to get acceptable results:

It was a fun but challenging exercise. For those unfamiliar with the BSP technique there is a quick explanation of it at the roguebasin wiki. The primary reason I chose this method of generation is because it doesn't rely on any pathfinding to get the job done, and generally has a clean look and feel to it (mostly straight halls). I went into it thinking it would be a piece of cake but fell into a number of pitfalls along the way. These were mostly due to poor coding decisions, including inconsistency with the collision and rasterization code (which resulted in halls protruding into rooms and other off-by-one nuances) and lack of abstraction across the x and y axes (which resulted in a lot of duplicate code that bred bugs like week old soup). I ended up rewriting about half the generator which helped immensely, and I was able to iron out the original bugs and get it "right" without relying on a bunch of last second hacks to work themselves out.

Now I could go into a lot more detail about the algorithm itself, but I guess the point I'm really trying to make is no matter how you choose to go about something new like this you'll never seem to run out of problems you didn't expect. Don't be afraid to take a few steps backwards because your subsequent attempts will certainly benefit from your mistakes. This is especially important with procedural content because you can't make too many assumptions. A bit of code may work perfectly 99% of the time but one day the stars align and it breaks the game and you're like "Well fuck, this changes everything". It's especially dangerous when your logic appears correct and incapable of producing such results, and you can get stuck trying to fix it as is. If all else fails, re-approaching the whole problem with the bug in mind offers the best chance of ensuring it doesn't happen again.