Create a shape with the fill and stroke the way you want. Open the Graphic Styles window and using the selection tool, drag the art onto the first swatch listed, holding down Option/Alt when you release the mouse button. You have just changed the defaults.

If you want to change it for any new document, there's a recent blog entry which details this. See:

http://www.astutegraphics.com/blog/how-to-create-a-template-document-w ith-default-path-settings-in-adobe-illustrator/

DF

So when you have your gray black that is your default selected, what does your color panel tell you it's percentages are?  It should be 0,0,0 if you're in RGB mode.  When I look at the color picker in RGB when I am in CYMK mode, I end up with 35,31,32 - Are you seeing something along those lines?

The Color panel and the Document Color Mode are two different things.  (Just because your picker is in RGB doesn't mean your document is) You can see what color mode you're in, and switch to the other one if necessary, from the File menu.  Be aware that your colors will shift when going between the different modes. There are colors in RGB that CMYK cannot reproduce, and vice versa.

So just to be clear - when you make a new document, you either specify that it's for the web or you manually change the color mode?  Otherwise, you are making a CMYK document.

If you really are in RGB color mode, as indicated in your file menu (screenshot showing CMYK mode below) and you hit "d" to get your defaults back and get a black in the RGB picker that is not 0|0|0, there is something awry.  Have you tried deleting your preferences?  If that doesn't fix it, then you need to check your default template files.  What version of Illustrator are you running?

And what did you do to set the default to be to your liking in that one document?