I have a few Ideas:
1. How big is the file you're working with? If you're working at the dpi you're going to print at, you won't have any unintended fuzziness.
2. In the Layers dialog box, double click the shape you created, probably "Shape 1". Make sure the blend mode is normal and the opacity and blend sliders are at 0 or 100%. Fiddle around, see what PS can do.
3. I agree with patrickl, there's no need to paint your oval. You just go double click the box on the left size of the shape 1 layer and get a "color picker" where you can change the color.
4. I just made an oval, and when I tried to paint it, it first needed to rasterize the shape. Then it filled my oval with the new color and it was pretty sharp. Make sure your paint bucket tool isn't set to a mode that paints fuzzily.