I started studying Japanese in 1998, and last year, 2008, I began feeling completely comfortable and confident with Japanese. It took me about 10 years.
Charlie Rose has interviewed various accomplished men and spoke with them regarding talent. One interview with Geoff Colvin, author of "Talent is Overrated" (ISBN: 978-1591842248), Geoff talked about "deliberate practice" and a 4/6/10 phenomenon (4 hours a day, 6 days a week, for 10 years).
Once I became able to speak without focusing on grammar and vocabulary, and became able to focus on the person I am speaking with, I felt like I made a huge leap towards native fluency.
A good test of confidence for me is seeing how I react when someone says something negative about my Japanese.
If you can do the following, you pass the test, and are to large extent confident.
1. Not feel terribly insulted or hurt, and confidently reject that the comment is a reflection of your lingual ability
2. Understand their position or their reason for their comment, and that their comment may reflect how they percieve you or thier internal emotional state.