I"m shooting for 2000, but I'll probably end up around 2500 which I really think should be acceptable for any reasonably recent graphics card nvidia 6800 or better.
512x512 is a rather small texture but it can be done, you won't be able to see a belt buckle very well and eyes just become dots, but it can be done. The problem is that normal maps that small are almost useless for a character. The details just disappear. Any detailed texture will show pixels pretty badly but the normal map will only show large objects.
When creating a character texture, I'll work with an image of no less than 4096x4096 and usually larger depending on the amount of detail. Then reduce it to the necessary size and fix any bad pixels with a smudge or blur brush. Sometimes I have to actually go in and paint pixel by pixel but usually only around the eyes or on any small details.
Oh, and the character I am working on I'll keep progress here
http://forums.alientrap.local/viewtopic.php?t=3128