Did he use his original first name? Sometimes you can search by first name and date of birth to narrow down some possibilities. He may have changed only part of his surname, or kept it similar to the original, in which case a Soundex search may catch it.
If you want to post his name, DOB, etc. as you know it, someone may be able to assist.