Why is sampling non-uniformly from the replay memory an issue? (Prioritized experience replay)
The problem is not that we need importance sampling because the learning is off-policy -- you are correct in that for one step off-policy algorithms such as $Q$-learning we don't need importance sampling, see e.g. here for an explanation why. The reason we need the importance sampling is due to the loss used to train the network.
In the original DQN paper, the loss is defined as
$$L_i(\theta_a) = \mathbb{E}_{(s,a,r,s') \sim \mbox{U}(D)} \left[ \left( r + \gamma \max_{a'} Q(s',a' ; \theta_i^-) - Q(s,a;\theta_i) \right)^2 \right ]\;.$$
You can see here the expectation over the loss is taken according to a uniform distribution over the replayed buffer $D$. If we started randomly sampling non-uniformly, as is the case in PER, then the expectation wouldn't be satisfied and would introduce bias. Importance sampling is used to correct this bias.
Note that in the paper they mention that the bias isn't as much of an issue at the start of learning and hence they use a decaying $\beta$ that only makes the importance sampling weights the 'correct' weights to use at the end of learning - this means that the estimate of the loss is asymptotically unbiased.