Generalized Euler sum $\sum_{n=1}^\infty \frac{H_n}{n^q}$
$$ \begin{align} &\sum_{j=0}^k\zeta(k+2-j)\zeta(j+2)\\ &=\sum_{m=1}^\infty\sum_{n=1}^\infty\sum_{j=0}^k\frac1{m^{k+2-j}n^{j+2}}\tag{1}\\ &=(k+1)\zeta(k+4) +\sum_{\substack{m,n=1\\m\ne n}}^\infty\frac1{m^2n^2} \frac{\frac1{m^{k+1}}-\frac1{n^{k+1}}}{\frac1m-\frac1n}\tag{2}\\ &=(k+1)\zeta(k+4) +\sum_{\substack{m,n=1\\m\ne n}}^\infty\frac1{nm^{k+2}(n-m)}-\frac1{mn^{k+2}(n-m)}\tag{3}\\ &=(k+1)\zeta(k+4) +2\sum_{m=1}^\infty\sum_{n=m+1}^\infty\frac1{nm^{k+2}(n-m)}-\frac1{mn^{k+2}(n-m)}\tag{4}\\ &=(k+1)\zeta(k+4) +2\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{(n+m)m^{k+2}n}-\frac1{m(n+m)^{k+2}n}\tag{5}\\ &=(k+1)\zeta(k+4)\\ &+2\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{m^{k+3}n}-\frac1{(m+n)m^{k+3}}\\ &-2\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{m(n+m)^{k+3}}+\frac1{n(n+m)^{k+3}}\tag{6}\\ &=(k+1)\zeta(k+4) +2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}} -4\sum_{n=1}^\infty\sum_{m=1}^\infty\frac1{n(n+m)^{k+3}}\tag{7}\\ &=(k+1)\zeta(k+4) +2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}} -4\sum_{n=1}^\infty\sum_{m=n+1}^\infty\frac1{nm^{k+3}}\tag{8}\\ &=(k+1)\zeta(k+4) +2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}} -4\sum_{n=1}^\infty\sum_{m=n}^\infty\frac1{nm^{k+3}}+4\zeta(k+4)\tag{9}\\ &=(k+5)\zeta(k+4) +2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}} -4\sum_{m=1}^\infty\sum_{n=1}^m\frac1{nm^{k+3}}\tag{10}\\ &=(k+5)\zeta(k+4) +2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}} -4\sum_{m=1}^\infty\frac{H_m}{m^{k+3}}\tag{11}\\ &=(k+5)\zeta(k+4) -2\sum_{m=1}^\infty\frac{H_m}{m^{k+3}}\tag{12} \end{align} $$ Letting $q=k+3$ and reindexing $j\mapsto j-1$ yields $$ \sum_{j=1}^{q-2}\zeta(q-j)\zeta(j+1) =(q+2)\zeta(q+1)-2\sum_{m=1}^\infty\frac{H_m}{m^q}\tag{13} $$ and finally $$ \sum_{m=1}^\infty\frac{H_m}{m^q} =\frac{q+2}{2}\zeta(q+1)-\frac12\sum_{j=1}^{q-2}\zeta(q-j)\zeta(j+1)\tag{14} $$
Explanation
$\hphantom{0}(1)$ expand $\zeta$
$\hphantom{0}(2)$ pull out the terms for $m=n$ and use the formula for finite geometric sums on the rest
$\hphantom{0}(3)$ simplify terms
$\hphantom{0}(4)$ utilize the symmetry of $\frac1{nm^{k+2}(n-m)}+\frac1{mn^{k+2}(m-n)}$
$\hphantom{0}(5)$ $n\mapsto n+m$ and change the order of summation
$\hphantom{0}(6)$ $\frac1{mn}=\frac1{m(m+n)}+\frac1{n(m+n)}$
$\hphantom{0}(7)$ $H_m=\sum_{n=1}^\infty\frac1n-\frac1{n+m}$ and use the symmetry of $\frac1{m(n+m)^{k+3}}+\frac1{n(n+m)^{k+3}}$
$\hphantom{0}(8)$ $m\mapsto m-n$
$\hphantom{0}(9)$ subtract and add the terms for $m=n$
$(10)$ combine $\zeta(k+4)$ and change the order of summation
$(11)$ $H_m=\sum_{n=1}^m\frac1n$
$(12)$ combine sums
Answering the first part of the question for $q$ odd we recall from the following MSE post the identity: $$ H_n = - \frac{1}{2\pi i} \int_{-1/2-i\infty}^{-1/2+i\infty} \zeta(1-s) \frac{\pi}{\sin(\pi s)}\frac{1}{n^s} ds.$$ The proof at the above cited post is sound and I will merely refer to it here since otherwise we would just include it verbatim.
This gives the formula for your sum: $$\sum_{n\ge 1} \frac{H_n}{n^q} = - \frac{1}{2\pi i} \int_{-1/2-i\infty}^{-1/2+i\infty} \zeta(1-s) \frac{\pi}{\sin(\pi s)} \zeta(q+s) ds.$$
Now shift this integral to the left to the line $\Re(s) = -1/2-(q-1),$ getting $$\sum_{n\ge 1} \frac{H_n}{n^q} = \rho_1 - \sum_{k=1}^{q-2} \zeta(1+k) (-1)^k \zeta(q-k) - \frac{1}{2\pi i} \int_{-1/2-(q-1)-i\infty}^{-1/2-(q-1)+i\infty} \zeta(1-s) \frac{\pi}{\sin(\pi s)} \zeta(q+s) ds$$ where $$\rho_1 = \operatorname{Res}\left( -\zeta(1-s) \frac{\pi}{\sin(\pi s)} \zeta(q+s); s=-(q-1)\right).$$
Make the substitution $t=s+(q-1)$ in the integral to get (not including the minus sign in front) $$ \frac{1}{2\pi i}\int_{-1/2-i\infty}^{-1/2+i\infty} \zeta(1-(t-(q-1))) \frac{\pi}{\sin(\pi (t-(q-1))} \zeta(q+t-(q-1)) dt.$$ For $q$ odd this simplifies to $$ \frac{1}{2\pi i}\int_{-1/2-i\infty}^{-1/2+i\infty} \zeta(q-t) \frac{\pi}{\sin(\pi t)} \zeta(t+1) dt.$$ Now make another substitution, namely $v=-t$, to get $$ \frac{1}{2\pi i}\int_{1/2+i\infty}^{1/2-i\infty} \zeta(q+v) \frac{\pi}{\sin(\pi v)} \zeta(1-v) dv =-\frac{1}{2\pi i}\int_{1/2-i\infty}^{1/2+i\infty} \zeta(q+v) \frac{\pi}{\sin(\pi v)} \zeta(1-v) dv$$ where the minus on the sine term cancels the one on the differential. Finally shift this integral to the line $\Re(v) = -1/2$ to obtain $$\rho_2 - \frac{1}{2\pi i}\int_{-1/2-i\infty}^{-1/2+i\infty} \zeta(q+v) \frac{\pi}{\sin(\pi v)} \zeta(1-v) dv = \rho_2 + \sum_{n\ge 1} \frac{H_n}{n^q}$$ where $$\rho_2 = \operatorname{Res}\left(- \zeta(1-v) \frac{\pi}{\sin(\pi v)} \zeta(q+v); v=0\right).$$ We have shown that $$\sum_{n\ge 1} \frac{H_n}{n^q} = \rho_1 - \sum_{k=1}^{q-2} \zeta(1+k) (-1)^k \zeta(q-k) - \left(\rho_2 + \sum_{n\ge 1} \frac{H_n}{n^q}\right).$$ This gives $$ \sum_{n\ge 1} \frac{H_n}{n^q} = \frac{1}{2} (\rho_1-\rho_2) - \frac{1}{2} \sum_{k=1}^{q-2} \zeta(1+k) (-1)^k \zeta(q-k).$$ To conclude introduce $$ W(s) = -\zeta(1-s) \frac{\pi}{\sin(\pi s)} \zeta(q+s).$$ This implies that $$ W(-s-(q-1)) = -\zeta(s+q) \frac{\pi}{\sin(\pi (-s-(q-1)))} \zeta(1-s) = - W(s)$$ because $q$ is odd. Now $$\rho_2 = \frac{1}{2\pi i} \int_{|s|=1/2} W(s) ds.$$ Put $s = -t -(q-1)$ and note that this does not change the counterclockwise orientation of the circle induced by the first integral to get $$ -\frac{1}{2\pi i} \int_{|-t-(q-1)|=1/2} W(-t-(q-1)) dt = \frac{1}{2\pi i} \int_{|-t-(q-1)|=1/2} W(t) dt = \rho_1$$ because $|-t-(q-1)|=|(-1)(t+(q-1))|=|t-(-(q-1))|.$ The conclusion is that $$ \sum_{n\ge 1} \frac{H_n}{n^q} = -\frac{1}{2} \sum_{k=1}^{q-2} \zeta(1+k) (-1)^k \zeta(q-k)$$ for $q$ odd.
Addendum. Sun Apr 27 23:57:35 CEST 2014 I don't quite see why I didn't simply evaluate the residues $\rho_1$ and $\rho_2$ as these are both easy. This does not affect the correctness of the argument.
Addendum. Sun Nov 9 23:33:24 CET 2014 In fact the equality of the two residues follows by inspection. In retrospect it appears I wanted to avoid working with the two double poles and keep everything within the limits of pen and paper.
When $q$ is odd and greater than $1$, one can show $$ \sum_{n=1}^{\infty} \frac{H_{n}}{n^{q}} = \frac{1}{2} \sum_{k=1}^{q-2} (-1)^{k-1} \zeta(k+1) \zeta(q-k)$$
by replacing $H_{n}$ with the integral representation
$$ H_{n} = \int_{0}^{1} \frac{1-x^{n}}{1-x} \, dx \ ,$$
switching the order of integration and summation, and then repeatedly integrating by parts.
This result is also derived in Marko Riedel's answer using a different approach.
$$ \begin{align} \sum_{n=1}^{\infty} \frac{H_{n}}{n^{q}} &= \sum_{n=1}^{\infty} \frac{1}{n^{q}} \int_{0}^{1} \frac{1-x^{n}}{1-x} \, dx \\ &= \int_{0}^{1} \frac{1}{1-x} \sum_{n=1}^{\infty} \frac{1-x^{n}}{n^{q}} \, dx \\ &= \int_{0}^{1} \frac{\zeta(q)- \text{Li}_{q}(x)}{1-x} \, dx \\ &= - \Big(\zeta(q) - \text{Li}_{q}(x) \Big) \ln(1-x) \Bigg|^{1}_{0} - \int_{0}^{1} \frac{\log(1-x) \text{Li}_{q-1}(x)}{x} \, dx \\ &= -\color{#C00000} {\int_{0}^{1} \frac{\log(1-x) \text{Li}_{q-1}(x)}{x} \, dx} \\ &= \text{Li}_{2}(x) \text{Li}_{q-1}(x) \Bigg|^{1}_{0} - \int_{0}^{1} \frac{\text{Li}_{2}(x) \text{Li}_{q-2}(x)}{x} \, dx \\ &= \zeta(2) \zeta(q-1) - \int_{0}^{1} \frac{\text{Li}_{2}(x) \text{Li}_{q-2}(x)}{x} \, dx \\ &= \zeta(2) \zeta(q-1) - \text{Li}_{3}(x) \text{Li}_{q-2}(x) \Bigg|^{1}_{0} + \int_{0}^{1} \frac{\text{Li}_{3}(x)\text{Li}_{q-3}(x) }{x} \, dx \\ &= \zeta(2) \zeta(q-1) - \zeta(3) \zeta(q-2) + \int_{0}^{1} \frac{\text{Li}_{3}(x)\text{Li}_{q-3}(x) }{x} \, dx \\&= \zeta(2) \zeta(q-1) - \zeta(3) \zeta(q-2) + \zeta(4) \zeta(q-3) - \int_{0}^{1} \frac{\text{Li}_{4}(x) \text{Li}_{4-q}(x)}{x} \, dx \\ &=\zeta(2) \zeta(q-1) - \zeta(3) \zeta(q-2) + \zeta(4) \zeta(q-3) - \ldots + \zeta(q-1) \zeta(2) - \int_{0}^{1} \frac{\text{Li}_{q-1}(x) \text{Li}_{1}(x)}{x} \, dx \\ &= \sum_{k=1}^{q-2} (-1)^{k-1} \zeta(k+1) \zeta(q-k) + \color{#C00000}{\int_{0}^{1} \frac{\log(1-x) \text{Li}_{q-1}(x)}{x} \, dx} \end{align}$$
Therefore, if $q$ is odd,
$$\sum_{n=1}^{\infty} \frac{H_{n}}{n^{q}} = - \int_{0}^{1} \frac{\log(1-x) \text{Li}_{q-1}(x)}{x} \, dx = \frac{1}{2} \sum_{k=1}^{q-2} (-1)^{k-1} \zeta(k+1) \zeta(q-k).$$