Group nodes by terms
In your view add two fields:
- Node title
- Taxonomy Term

You are right up to here.

Now:


Set the "Taxonomy Term" field to "Exclude from display"
Select your views' format as unformatted list; use "Edit settings" for the format
Set "Grouping Field" as "Taxonomy Term"


For details, view my views' export data in pastebin.