The thing they wanted me to do was maximum priority, but there was also some other totally unpredictable thing (often support related) that I also had to take care of. The higher-up was 100% sure it wasn't a real problem and assumed I was exaggerating the situation.
The solution to the problem of lack of trust is of course to convince them, or to leave. If you can't make changes that increase your productivity, you'll become stressed and burned out, and will still not be able to do enough. It is a decision they made.