I would like to differentiate the look as much as I can but yet it has to be within the limits of what is reasonable for a single programmer can do. I have alot of ideas that would make the game itself different but I'm afraid the look of the blocky world and blocky characters are going to be too much like Minecraft. I've toyed around with the idea of giving the characters big heads, or skinny bodies, or elbows and knees.
You shouldn't be worried if a game 'looks' like another. Take Terraria; early alpha screenshots, people were 'ZOMG IT IS A MINECRAFT CLONE'. It gets released - obviously not like Minecraft at all.
Then take something like FortressCraft - that is obviously a Minecraft clone. It has the same features, pretty much. The graphics have changed, maybe.
As long as the core concept is different, and the graphics are different enough so that you would not confuse the two, you will not have a problem. Maybe try a realistic style person, instead of a blocky one?
If you end up stuck with overall body shapes that look like Minecraft's, your textures can help you stand apart. Without knowing your game's goals and limitations, you could use:
-Higher or lower resolution textures.
-High-contrast textures (think Tron)
There are lots of games done in pixel-art style that have interesting characters that stand out. And this is an odd time, just after Minecraft came out. For a while, everything will be compared to it, but eventually it will just be the first in a series of games in this genre/style. Maybe yours could be the other game we all compare to. :)
I think Minecraft is almost a genre, at this point. There are many success where people are taking the core concept adding something new. But you have to find the core mechanic that differentiates you from the original.
I would mention a few specific games (such as Stonehearth, which is where most of the Qubicle character images come from) but there are a ton of games, art (e.g. on DeviantArt), demos, movies, etc that use different styles. Hence, I suggest an image search.
blocky characters, and
"qubicle" characters. (Yes, put "qubicle" in quotes, or else your search engine might think you meant "cubicle" and give you other random stuff.) Qubicle is an app for creating voxel models, in the sense of "volumetric pixel" instead of the "textured cube" model that Minecraft is.
You'll find that there a lot of different ideas of how to create characters in a low-res, 8-bit, and/or boxy style without being stuck with Minecraft's aesthetics. An image search will show you a wide range of styles, and if you're working with an artist they can riff on a few of your favorites to come up with something new.
Yes, If you take a loot at blockstorm characters are done by cubes, but they look much more serious than minecraft.
I think the trick is using enough cubes to approximate a real Surface. Of course if you do not limit to cubes but to prism or even use lowpoly models you can still make stuff that appears creepy and serious (I'm thinking to the first First person shooters using polygonal enemies).
You should search some artist specialized in voxel art, I've seen on internet some very cool artworks.