Your guess is correct. You can only say $e$ and $f$ have the same trace if your $M$ is a factor. To see this, any finite dimensional $M$ is isomorphic to a direct sum of full matrix algebras, say
$$
M = \bigoplus_{j=1}^k M_{m_j}(\mathbb{C}).
$$
By uniqueness of the normalized trace on $M_n(\mathbb{C})$, we see that normalized faithful traces on $M$ are in bijective correspondence with vectors $(t_1,\dots, t_k)$ with strictly positive entries such that
$$
(m_1,\dots, m_k) \cdot (t_1,\dots, t_k) = \operatorname{tr}(1) = 1.
$$
Note that $t_j$ is the trace of a minimal projection in the summand $M_{m_j}(\mathbb{C})$ of $M$.
(Here, I've used the notation from Jones' Index for subfactors [MR696688], Section 3.2.)
So now we can build a concrete counterexample. Let $M = M_2(\mathbb{C}) \oplus \mathbb{C}$, with trace vector $\vec{t} = (3/8,1/4)$. Let $e$ be a minimal projection in the $M_2(\mathbb{C})$ summand, which has trace $3/8$, and let $f$ be the minimal projection in the $\mathbb{C}$ summand, which has trace $1/4$.