EDIT. In light of Nathaniel's answer above, I must admit that the hardness intuition was wrong, and the problem is indeed tractable. However, I'm leaving the original answer as is, to preserve the context.
Too long for a comment, but some background information that suggests why it might be usually very hard to compute $\|T\|_{\text{S}}$.
The following theorem is usually attributed to Haagerup (though the Davidson paper cited above suggests that it was already known to previous authors, and it could also be essentially attributed to Grothendieck).
Thm. Let $T$ be any matrix. Then \begin{equation*} \|T\|_S = \min\{ \|X\|_{\infty,2} \|Y\|_{\infty,2} \mid T = X^*Y\}, \end{equation*} where $\|\cdot\|_S$ denotes the Schur-multiplier norm, while $\|X\|_{\infty,2} = \max_{1 \le j \le n} \|x_j\|_2$, where $x_j$ is the $j$-th column of $X$.
If $T$ is unitary, then $\|T\|_S=1$; if $T$ is symmetric positive definite, then $\|T\|_S = \max_i t_{ii}$. For many other special matrix structures, this norm can be computed, and the Davidson paper linked to in my comment to the OP provides several such examples.