I feel you are mixing the two (experienced users and thinkaloud) for no good reason.
First-time vs experienced
I assume by your post that your main goal for the evaluation was to identify usability problems.
There is absolutely nothing that states that only first-time users meet the fit-criteria for such purpose. It really depends whether you wish to evaluate the usability for first time users or for experienced ones, which in turn will depend on whether the site was designed more towards this group or the other (sites designed for repeated use, like gmail, may intentionally sacrifice usability for first-time users to gain better usability for frequent users).
Having said that, evaluating with first-time users will nearly always reveal more usability problems than doing so with experienced users (and again, some of these problem may be irrelevant if the site was designed for the latter group). But you'll be surprised how many usability problems you can identify on some systems, even if the participants are daily users with 3 years of mileage.
Thinkalouds
Thinkalouds are used in evaluation to probe into people minds - to learn what they think first hand, rather than having to subjectively interpret their actions and responses by mere means of observation.
Needless to say, thinkalouds introduce problems of their own, like being a massive hurdle for measurements taking, or the interference itself with puts the whole event even further from a real-world usage.
Whether thinkalouds are done on first-time or experienced users matters not. But like in the previous case, you would typically have greater insights with first-time users - with experienced ones, you are in danger of "I know because I've used it before" type of statements. Yet you can use probing "What would you call it?" to further investigate things.
Answers
Are my results still valid findings?
It is impossible to answer without seeing the goals, the process, the results, and your analysis. But if it seems to you unreasonable that you have found usability problems with experienced users - please consider it highly reasonable.
Is it fine conducting Think Aloud test with users familiar with the interface?
It is. In your case, the experienced users is the problem, not the thinkaloud.
What should I have done differently?
It is hard to answer without information about the goals of the evaluation. But seems like you know well that choosing the right participants was key in your case.
As a small tip, when preparing for an evaluation, it is may be easier to start thinking about the exclusion-criteria only then worry about the fit-criteria.
