Remove nodes you don't want, backup DB, purge DB data dir, stop / start server, reinsert DB, enjoy.
I tried following on both Firefox and Chromium and it didn't work:
- removing all nodes of types I no longer used
- clearing localStorage neo4j.grass key - it does contain labels, but this doesn't help
- clearing whole localStorage (completely)
- stopping / killing server and bringing it back after points above
- removing files with labels in their names from DB data dir
- removing all neo4j cookies (in fact, later, whole browser cache as well)
Since purging DB and reinserting data worked, and since clearing local storage and launching another browser gets you same labels you had, I'm guessing the info is held partially in localStorage AND partially in files in graph.db dir (or however your DB dir is called). Files there are often binary, so I picked redoing whole DB (since it wasn't big anyway) over blind edits or decoding binaries - simply faster.
EDIT:
You may try something I've just spotted:
label > properties > view Stylesheet > click on drop icon (looks like extinguisher). This should drop the grass key.
You may need to have at least one node of given type for that, to open a view where you actually set up node display (colors and other properties) to get to it's stylesheet.