Graphics look absolutely beautiful!
I'd make a "Seige Defense" game. Your objective is to defend a town, person (king), or holy relic from invaders.
Enemies attack in waves which can occur either in day or night. There should be a time countdown until the next wave displayed in the corner of the screen.
Enemies are able to break down walls, tunner underground, or climb over walls to attack you (currenlty in minecraft they can't do to those things) There should be an emphasis on terrain destruction: catapults, cannons, bombs, fires, battering rams, etc. Enemies AI should look for weak points in your structure and concentrate force there. Enemies may also use seige towers, grappling ropes, or even blimps to get over your walls.
As with Minecraft, there are 3 basic things you can do in this game: mine, build/repair, and fight. There are Non-Player Characters (NPCs) on your team also performing these jobs, i.e. miners, builder, and soldiers. These guys do their job at a slower rate than can, so you need to give them orders of where to defend, dig, build, etc. See the game "Dungeon Keeper" for some ideas on this.
Miners should have a finite capacity of materials they can hold before they must return to base (or unload it to a mining cart), so you'll have to build walls to protect your mine supply lines. In the game you'll need to choose between defending your resource lines, adding new towers to your base, or reinforcing existing walls.
Materials like brick and stone will be damage resistant, but will be more expensive. There can also be NPCs with whom you can trade (buy/sell) for resources. Some rare resources can only be obtained through trading, which are needed for rare items/weapons.
Food/farming/water within the town could also play a role. For example if you run out of food, you lose the seige.
Watch the movie "Kingdom of Heaven: Directors Cut" for some ideas (last ~25% of the movie or so)