I have to agree - even if it's not trademarked, your going to get users confused between their app and yours. Find something unique and trademark that instead.
Ah, ok, that's different. A trademark has 'scope'. The right time would be when you've settled on a name, before you invest into marketing that name to the general public.
Disclaimer: Consult an IP lawyer or patent attorney
Scope typically applies to specific industries.
To the original poster, you do risk legal action - even if you have a registered trademark and they don't. They probably have a common law trademark (which does not need to be registered) that predates yours.
But look at it this way, letting go of it now is going to save you a ton of trouble later, in the long term you'll be off cheaper and there is no chance of confusion.
Also if the other party is 'bigcorp, Inc' then you're setting yourself up for a legal fight at a time when you probably have better things to do.
EDIT: A name can not be 'perfect' if it is already taken, the domain name is not free or if somebody else already has a lien on it or is shipping something under that name.
I think you need to re-think your concept of the 'perfect' name :)