Were, by any chance, any of the lines you selected
white or violet? If so, then no wonder it didn't work...
You see, when you select a line, the color of the line is different according to
how many faces the line is connected to. And so, if it's white or violet, then that means it's connected to two or more faces, and (for whatever reason) it can't fill.
Also, make sure the lines you selected are in a complete loop.
Would it be possible I could see a screenshot?