A) What program do YOU think he used to create the 3d concept art and video clips for final fantasy 13, 10 ect? My bet would be a custom made program, but im interested to know other peoples opinions. Since such information is undisclosed.
B) Any really good tutorials around for creating realistic 3d character designs for max or maya?
Well, i don´t think Square used a custom made 3D programm.
I guess it´s one of the big three one Maya, Max or XSI, with some self made scripts / plugins at least.
In fact it doesn´t matter what application they used, all provide almost the same kind of features you need. When you look to cgtalk.com you recognise that whatever software you use its all about your skills at the end.
So get whatever application you can afford or a comfortable with and start.
And as Bushido already mentioned, Anatomy is the key element of doing character modelling.
As for tutorials, I already wrote about cgtalk.com, which is as far as i know the biggest forum about cg (I guess you will get a answer there what application they used...) and finally google is your friend.
Are you sure Tetsuya Nomura is the one who modelled the character in your link?
I always thought Nomura was only in charge of painting the characters and that it was up to other guys to do the 3D stuff.(?)