Leave the blue! It's a very nice color!
Things I'd change, though:
1. Enhance the logo a bit and combine it with your saying. If I were you, I would make the letters "Cheatpark" bigger in your design, and make the words, "Gaming at its best" a part of it. Don't have it off to the side; it doesn't look cool! I'd also make the logo "Cheatpark.net," so people remember the URL better. (See attachment)
2. The others are right about the navigation. Here's a possible solution: you could try to do it a la,
Ugo.com. You could maybe have "| Chat | Forum | Links | Advertising | Guestbook | Support | " in a black navbar going across the width of your page like Ugo, then have the other stuff ("News | Previews | Reviews | Cheats | Charts | Release dates | Downloads | Votes | ") linked on your index page using pictures and text to spruce it up!
Remove "newsletters" and "search" from your navigation, because they can simply be added to your site with text boxes.
3. Color scheme? Go with shades of blue, black, a little grey and bits of that orange from your logo to add unity.