I think a big part of the problem here is the idea that not only are governments responsible for protecting their own citizens, they are also only required to respect the basic rights of their own citizens. That inevitably leads to one of two conclusions if governments then feel entitled to conduct mass surveillance of everyone else's citizens.
One possibility is that those other people's own governments consider the surveillance a hostile act. Now everyone's government starts a cold war of information with everyone else's, even if they claim to be allies.
The other possibility is that those other people's governments do not defend their own citizens from the mass surveillance, or even actively collaborate in it despite their apparent obligations to their own population. Now people don't just have cause to mistrust foreign governments, even supposedly allied ones, but they can't even trust their own government to protect them.
Obviously neither of these outcomes is exactly taking the political or ethical high ground. But no-one seems to want to take a lead on what to me is the obvious third alternative: everyone accepting that we are all part of a global community today, and that international trade and communications and transportation are in all our best interests, and that which country's flag was flying when you were born probably has very little to do with whether you are a good person (probably) or a real danger (in which case everyone has legitimate grounds to go after you and already has processes in place to do so), and that because of that same level of international infrastructure and modern technology it should be just as possible to recognise everyone's basic rights by default and collaborate to go after legitimate surveillance targets anywhere instead of drawing artificial borders that are mostly accidents of history and creating a them-and-us culture that serves no-one.
Modern politics reminds me of a Babylon 5 episode, which seemed amusing at the time:
You should be pissed, and it pisses me off that my government is pissing you off, but that doesn't mean I think it needs to get warrants to spy on other countries.
I think there is a difference between committing illegal actions when they are inevitable (I can understand that, eg, the US would want to conduct targeted surveillance on known AQ members abroad). It's another thing to make it into an all-encompassing, industrial activity. And clearly, the distinction between "national" and "foreign" is rather... blurry. The US, the Europeans, the Australians, I assume Japan, Korean, Taiwan... look like they have a good working relationship, in which everybody can spy on everybody else, as long as you can pretend it's about security.
And where then does it stop? Should countries also not be required or require themselves to provide due process to citizens of other countries when they visit? How about not recognizing property rights, and confiscating their belongings? Why not go the whole way and just shoot the ones you don't like?
The reason that international human rights treaties exist is that adopting isolationist policy in the area of human rights is a move that creates no winners. We just seem to have forgotten that in the context of the Internet, because the violations take place at home while the immediate victims are abroad. But the indirect consequences will probably come back to haunt those who don't respect citizens of other nations all too quickly, whether it is in loss of tourist trade, or loss of control of technologies like the Internet because a single nation is no longer trusted to administer that technology impartially, or more direct consequences to the bottom line if for example technology companies with cloud-based offerings are no longer trusted by foreign customers.
The US seems to be particularly at risk today, because it has been a natural leader in some of these fields and has been trusted to act responsibly in that capacity. That trust is rapidly being eroded, and the US has more to lose as a consequence than most. Still, the general us-and-them attitude in today's international politics is a plague on all our houses.
Well, something like that is already considered quite legal, right? A Uruguayan citizen who buys some pot from his local government store and then boards a plane to Singapore isn't going to have a nice time in Singapore, even though by Uruguayan standards he's done nothing wrong: his property rights in that pot will not be recognized, at the very least, and probably he will be severely punished for something not considered a crime in his home country.
When country A is doing violence to the citizens of countries B and C inside country A, the usual response is merely that B and C recommend that their citizens not go to A. If the citizens were considered important, sometimes there's a protest of some sort.