I had more trouble gaining my initial UK passport as my birth certificate states BMH Dhekalia, the gentleman of foreign persuasion who dealt with the case at the Newport passport office said I was a cypriot not British and thus not entitled to a passport... Right up until I waived my 1250 under his nose and pointed out that it was/is a British Military base...
Never had an issue entering the USA though with Dhekalia on my passport though.