I created a new feature and performed a Uninstall/Remove/Add/Install-SPSolution using PowerShell to deploy it. The solution deployed correctly and the feature was added to the 14 hive, but did not appear in the UI until I performed an Update-SPSolution. Only after I performed this update was the feature usable.
Why on earth would an update be required in order to make the feature visible, when the solution has just been freshly installed?