I've been trying to re-create your problem, which has been difficult because the instructions work fine for me!
If you've definitely got the correct layer selected, the only reason that 'fill' should be greyed out is because Photoshop doesn't recognise that there's actually anything to fill.
The only way I could get a 'non-fillable' circle on the screen was if I selected the wrong tool. Are you sure that you've selected the Elliptical Marquee Tool, and not the Ellipse Tool? The circle you produce should have a 'shimmering' edge, to show that it's selected. (If you select the Ellipse Tool you get a circle which is both non-shimmering and non-fillable).
Chris