I think you can obtain an example by modifying the classical Toeplitz algebra.
$\newcommand{\H}{\mathbf{H}}$ 
$\newcommand{\bT}{\mathbf{T}}$
$\newcommand{\cT}{\mathcal T}$
 $\newcommand{\KH}{{\mathcal K}(\H)}$
 $\newcommand{\BH}{{\mathcal B}(\H)}$

Recall that ${\mathcal T} \subseteq \BH$ where $\H=\ell^2({\mathbf N}_0))$ and $\cT/\KH\cong C(\bT)$. Let $q: \cT \to C(\bT)$ be the corresponding quotient homomorphism, let $J=\{ f\in C(\bT) \colon f(1)=0\}$ and let $\cT_0= q^{-1}(J)$. More concretely, $\cT_0$ is the <strike>set of</strike> closed algebra generated by all Toeplitz operators $T_f$ for which the symbol function $f$ belongs to $J$.

Since $\cT_0$ quotients onto the commutative ${\rm C}^*$-algebra $J$ it has loads of tracial states (just pull back the states on $J$).

On the other hand, suppose $a\in Z(\cT)$. Then $[a,k]=0$ for all $k\in \KH$. But it is standard and not too difficult to show that if $b\in\BH$ satisfies $[k,b]=0$ for all $k\in\KH$, then $b$ is a scalar multiple of the identity. Since $q(I_\H)\notin J$ the only possibility is that $a=0$.