Is there any good tutorials out there for creating Brand New creatures with Blender, including and most importantly skeletons. Because I've been searching around and the best I could find is for 3DSMax.

You might find a tutorial or two on the http://tesalliance.org/forums/index.php?/forum/19-modeling/ forum at TES Alliance. If not, you can always ask there. :thumbsup:

http://cs.elderscrolls.com/constwiki/index.php/Blender/Custom_Creature

The tutorial Compulsion sent you is very good. I used it to create a custom creature myself, so I know it works. If you have any questions (some parts are a little tricky) just ask.