Building on what Toast said - you have two types of Trademark, registered designs, and unregistered designs, but they have to be distinctive. You're governed by the Trademark Act 1994, because you reside in Britain.
"In this Act a "trade mark" means any sign capable of being represented graphically which is capable of distinguishing goods or services of one undertaking from those of other undertakings."
The American Acts are very similar to this.
The long and short of it is that you can't trade under Deadboy in the US, because they already are, and have repuatation attached to that mark. You're not trading in the US (I think?), and have no reason to believe that anything they're doing infringes on your reputation in this country. The reverse is true of the other company - they can't come over here and trade.
To have it applied internationally, you need to file a convention trademark (there are international treaties covering intellectual property, including TMs and copyright) - but you can't do this if it infringes on another TM elsewhere - it's a very tricky area. If you're genuinely concerned about it, I'd speak to an IP lawyer.
Edit: You don't need to have registered anything to have a trademark, btw. This is why you see the (R) and TM signs - (R) is a registered trademark - TM is built up through reputation (very loose description).
You might run into sticky territory asking them to change their name if they've been around longer than you, so tread carefully.
