I have heard American children call this a "boat spoon". It does look a little like a boat.
The Chinese soup spoon is more of a ladle than a spoon. It has a flat bottom and steeply angled walls, and it holds a good mouthful of soup. It holds quite a bit more than your average Western soup spoon. In a way, it's a sort of one-sip soup bowl that you can pick up and hold to your lips.
More importantly, it holds one xiao3-long2-bao1 (also known as a "soupy bun"), and catches all the juice that bursts forth when you take your first bite. It's also useful for rescuing sunken treasures from the sargasso sea of your Cantonese wonton soup or Vietnamese pho. It is true that the angles between the flat bottom and the sides make it hard to lick clean in one sweep, but that means you get to lick several times and have more fun.
If the waiter tells you they don't have Chinese spoons, he evidently doesn't want your business. Put your money on the table, get up, and leave without further words. There is no point in making a scene, really. Life is too short for arguing about things that are obvious to everyone, and the need for a Chinese spoon is assuredly one of those.
Most Chinese spoons that I have seen are ceramic or sturdy plastic, suitable for lifting the heaviest objects you are likely to encounter in your soup. You can also find them in stainless steel, styrofoam, flimsy plastic (o beware of accidents!), and no doubt many other substances.