1. Faptul ca ai setat "Custom structure" in Settings > Permalinks > Sectiune "Common Settings", nu are legatura cu structura URL-urilor categoriilor... ci doar cu structura URL-urilor posturilor.
2. By default nu poti elimina category base-ul, de aceea e necesar plugin-ul (face modificari in rewrite rules).

LE: MaXz, cred ca deja a facut asta sau poate am inteles eu gresit.