The Windows console has always had only a 16-colors palette, and true console games have always worked with that.
If you still want to do it in C# (though I don't see the point), you'll have to draw your own "console", which is basically just a grid of characters (a 2D C# array, where each array element holds a character and a color). As for drawing this grid onto the screen, IMHO XNA is overkill. You could just use the System.Drawing class. If you're looking for reasons to learn XNA, you should find better ideas.
And what problems are you having with encoding console characters, exactly?
I'm trying to print some special characters (triangles, arrows and etc.). And on different computers I get different results - characters are printed, another characters printed or symbols "?" printed.
I guess it is problem with encoding and fonts.
I changed the font to Consolas, then to Lucida Console, but nothing changed (also, I changed Console.OutputEncoding to UTF8, then to unicode) and combine all of this settings.
The way using System.Drawning is usefull, but very simple for me - I want to use a Console....