We use expansion $$\frac{z-1}{z^{a+1}-1}=\frac1{a+1}\sum_{w^{a+1}=1} \frac{w(w-1)}{z-w}.$$
Now use Abel-Poisson regularization of your sum, multiplying $n$-th term by $t^n$ for $t<1$:
$$
\sum \frac{n-1}{n^{a+1}-1}=\frac1{a+1}\lim_{t\rightarrow 1-0} \sum_{w^{a+1}=1} w(w-1)\sum_n \frac{t^n}{n-w}.
$$
We have for $w\ne 1$ 
$$\sum \frac{t^n}{n-w}=\int_0^1 \sum_{n=1}^{\infty} t^nz^{n-w-1}dz=t\int_0^1 \frac{z^{-w}dz}{1-tz}.$$
Hence our sum equals
$$
\frac1{a+1}\int_0^1 \frac{\sum_{w^{a+1}=1} w(w-1)z^{-w}}{1-z}dz.
$$
This may be further rewritten in several ways. For example, we may replace $(1-z)^{-1}$ to $(1-z)^{\varepsilon-1}$ and then tend $\varepsilon$ to $+0$. For each single $w$ we get 
$$\int z^{-w}(1-z)^{\varepsilon-1}dz=B(1-w,\varepsilon)=\frac{\Gamma(1-w)\Gamma(\varepsilon)}{\Gamma(1-w+\varepsilon)}=\Gamma(\varepsilon)(1-\varepsilon \psi(1-w)+O(\varepsilon^2)).$$ 
Multiply this by $w(w-1)$ and sum up. Singularity $\Gamma(\varepsilon)$ goes out as expected, we get a sum like $$
\frac1{a+1}\sum_{w^{n+1}=1,w\ne 1} w(1-w)\psi(1-w).$$
Or just use the formula (proved by the same way) $\int_0^1 \frac{1-z^{-w}}{1-z}=\gamma+\psi(1-w).$