The Lost Millennium brought about a LOT of new cards that support Rocks. Megarock Dragon is a card that can only be Special Summoned by removing Rock monsters in your graveyard from play, and it then gains 700 attack for each monster removed for this effect. Not a bad trade off, especially since those monsters don't need to stay removed from play in order to boost Megarock. This is perfect bait for Return from a Different Dimension...though it would be better if there were more offensive Rocks out there, but oh well.
This deck has a lot of fun monsters to play with. Legendary Jujitsu Master is one of the most annoying cards in the game to face, and it can kill an opponent's tempo. Golem Sentry also is a great card to play - both of these cards remove the opponent's cards from the field, but instead of destroying them they get bounced back to the opponent. This is a very strong tactic, as this metagame is often about speed, and Rock decks force the opponent to slow down.
Maharaghi is an interesting card that is often overlooked. As a Spirit, it cannot be special summoned, so that makes it perfect bait for Gigantes or Megarock Dragon. On your Draw Phase after it has been summoned (or in most cases for you, flipped face up), you can view the top card of your deck before drawing, and place the card you see at the top or bottom of your deck. This basically allows you to choose what card you draw, and when used correctly this is a deadly tactic. Though you don't get to see what the next card is, if one card won't help you at ALL, you can place it back in your deck and hope for something better. Playtest it, and you will be surprised at the results.
Rock Bombardment is another decent card for this theme - it's a Trap that discards one Rock monster from your deck to your Graveyard, and deals 500 damage to the opponent. Using this card allows you to thin your deck and deal a little damage to the opponent. Better yet, it's chainable, so you'll be able to activate this if the opponent uses MST on it.
This deck could probably stand up to some of the top tier decks out there. Most of the cards in the deck control the tempo of the game, and Remove from Play is a tactic that is gaining a LOT of ground in today's game. Give Rocks a try if you get bored with the game - they have a lot of promise when played correctly.
Monsters - 19 (4 Tribute, 15 Non-Sacrifice)
Magic/Spells - 12
Traps - 9
