The key theorem (that you're missing) here is that the factors of the minimal polynomial correspond to the size of the largest associated Jordan block.
In this case, we know that the sizes of the largest Jordan blocks associated with each eigenvector of $A$ add up to $7$. However, $A,B$ are $8 \times 8$, which means that there's a block we haven't accounted for, and its size has to be $1$ so that the sum of all block-sizes is $8$.
So far, we've shown that $A$ and $B$ have to have the same Jordan blocks, except potentially for a size-$1$ Jordan block which they must have, but can be different for each without changing the minimal polynomial.
This is where we use the characteristic polynomial. Since the algebraic multiplicities are the same for $A$ and $B$, the eigenvalue of the remaining size-$1$ block has to be the eigenvalue corresponding to the factor in the characteristic polynomial that is missing from the minimal polynomial.
Thus, $A,B$ have to have the same Jordan form. So, they are similar.