USB connection type? Are you using Microsoft's built in disk manager or have you tried something like partition manager by a third party? if you haven't try that now and see if it will format to NTFS. They tend to be much more versatile then disk manger built into windows.
http://www.partition-tool.com/easeus-partition-manager/