Essentially this reduces down to if your situation merits filing a UDRP, which is the resolution process adopted by ICANN (the governing agency of TLDs like .com) for disputes over domain names.
In order to be successful in a UDRP, you need to establish three elements:
The domain name is identical or confusingly similar to a trademark or service mark in which the complainant has rights;
The registrant does not have any rights or legitimate interests in the domain name; and
The registrant registered the domain name and is using it in "bad faith".
For the first element, if the registrant began using the domain as a mark in their respective country prior to your trademark registration, they could seek to block your trademark application there based on their earlier usage. If your trademark was approved however, the panel would have to weigh whether you had rights to the mark based on your own prior usage, which is not always so cut-and-dry (i.e., you'd need to supply evidence to support these claims).
For the second element, you would need to demonstrate that the registrant didn't have a legitimate interest in the domain, which unfortunately, serving ads would likely qualify for as even Registrars do this.
For the third element, you'd have to demonstrate they registered the domain in attempt to interfere with your business, redirect traffic, or bought it only the purpose of selling it back to you, etc... This can be difficult to prove, especially if they're using it to serve content with (even ads).
So based on the above, it seems unlikely that you'd prevail in a UDRP case, which can be an expensive and laborious process to go through.
Note that being unsuccessful in a UDRP does not preclude you from filing legal suit in your local jurisdiction however, if you feel your rights and business has been impacted by the other party. That too however is a costly avenue to go down, which is why many domain squatters will price their registered domains at or below the legal expense for pursing that route.
Negotiations, or simply registering another domain, such as one of the new gTLDs coming available would be your best options.
Tip: If you're negotiating for a domain, do so anonymously.
