I found the issue, eventually. Sorry for the trouble!
It was actually Piotnet Grid, updated to version 1.0.24.
The code creating custom taxonomies works fine (I tested with PHP snippet inserter after I copied it from MetaBox). There was just some conflict with Piotnet Grid 1.0.24.
