I normally prefer Wicd over NM in most Linux installs I work on, but I'm now setting up a computer that I intend to use at least partially with a 3G dongle, and Wicd doesn't support them.

Accordingly I'd like to keep Wicd for connecting to wifi networks and NM for 3G ones, but it seems there's some key conflict between them as whenever I've installed Wicd the only way to make it work right was to uninstall NM altogether.

Can both of them be kept on the same install, or is it necessarily a Highlander thing ("there can be only one!")?

You haven't mentioned which distro you are using, but yes, in my experience indeed "there can be only one!"

It is unnecessary and, indeed, asking for a conflict, to have more than one network manager application.

CAN they, yes, if you set one of them to not manage the interfaces so it's installed but managing nothing at all. Which makes it useless. So is there any reason for them to? No. As mentioned, it is only asking for issues if they're both actively trying to manage things.