3) Moving entries into new categories appears to work, but the categories are empty when browsed directly.

Sorry for the issues, I found major issues too when digging deeper also. It's a very complex system code-wise and I think people usually only test it superficially as the options are pretty complicated. It's no wonder you got mixed up.

"Narrow-in" was not working at all. Now fixed.

Sorting was not working at all. Now fixed.

We'll release a new patch release very soon.

[quote]
Tree view vs Standard view (switching between them messes things up).
[/quote]

It will flatten your categories if you switch from a tree catalogue to a non-tree catalogue, and that cannot be undone. I don't consider that a bug, it's the natural effect of what you're doing.
Some proposed improvements are covered in #2426.

[quote]
Sort key and search key (has to be both, can't be one of the other)
[/quote]

Covered in #302.

[quote]
I didn't like the categories being listed as well
[/quote]

You can edit CATALOGUE_DEFAULT_CATEGORY_SCREEN.tpl, remove:
[code]
{+START,IF_NON_EMPTY,{SUBCATEGORIES}}
<div class="box box___catalogue_category_screen"><div class="box_inner compacted_subbox_stream">
<h2>{!SUBCATEGORIES_HERE}</h2>

<div>
{SUBCATEGORIES}
</div>
</div></div>
{+END}
[/code]

[quote]
As the categories somehow ended up being children on the main catalogue category that appeared, I had 2 lots of the same categories so I deleted the ones listed at root.
[/quote]

I can't follow here.
A tree catalogue has one single root, always. And you can't delete it. Maybe you meant "top-level categories". And a category can only be in one place, there's only a single parent for a category.

Anyway, hopefully you'll not be confused after the "narrow-in" bug fixes.

Just mentioning here again that there are issues created when switching from tree to non tree catalogues, maybe switching shouldn't be an option. I always tend to find myself with categories at the root and underneath the catalogue title when changing. This results in double the amount of returns for search terms as clearly the system is seeing double. The categories are listed alongside the parent, then below the parent, in your terms.

I just tested with a tree catalogue with 2 categories under root (so 3 categories).

So...
Root
Root > a
Root > b

I converted to non-tree and now I have 3 categories...
Root
a
b

So it seems normal and fine to me. I'd need to see a thorough step-by-step bug report (preferably a screencast) to understand what you're experiencing).

I suspect some kind of confusion still with category structure. Perhaps with deeper categories, and/or unwitting creation of duplicated category names.