FFF,
Call a FSDO and ask to speak to an inspector. Then call another FSDO and ask to speak to an inspector, if the stories match I'd say you had been given good advice. The FAA understands the concept of customer service.
If you have a US Social Security Number then that will be your certificate number unless you told them not to use it. In that case it will be a number the FAA generates. Did you rent using your permanent certificate? If so, the flying school probably has a copy, you could call them.
If you want a replacement certificate, and the original was based upon a UK licence, you need to have the CAA verify your details and you have to turn up to a FSDO for the replacement. I'd just get a visa and an unrestricted FAA CP-ASEL when you come over for your JAA CPL.
You really want to fly solo when practicing for these ratings, you don't want an instructor next to you all the time. Instructors get in the way, and where is the fun in that?
Cheers