Indeed, from now on I will back up my phone to the cloud, wipe it before going over a border, then reinstalling after. It's the only sane thing to do.
"Oh, you brought an empty phone? Give me access to your cloud account. No? Ok, you're never entering our country. Bye."
But don't be mistaken, that based on the Snowden revelations, "they" may not have already had it, and needed another country's intelligence agency to access it first -- for them to get to whatever it might be, and possibly even use it against you, legally.
It's also quite unlikely that they can circumvent a basic `tar -c /dev/block/* | gpg -se ...` scheme that's trivially doable on unlockable Android phones. (Replacing the bootloader with a maliciously crafted variant that returns false partition data after bootup would work, but once again: CBSA.)
You're probably safe if you just do an iCloud backup and wipe followed later by a restore.
Certainly do replace the SIM card as soon as possible though, IMO. Unless you can verify it somehow.