A Hermitian matrix of dimension $N$ has $N^2$ real parameters. However, in the answer by rcollyer I see a larger number of parameters in the form of complex numbers (which means the representation isn't unique). In Heike's solution (which is from the [documentation for `HermitianMatrixQ`][1]) we have to write `Re[n]` on the diagonal which is OK in principle but creates the impression as if `n` as a complex number has significance, which of course it doesn't. 

So one should be able to specify the real-valuedness of the diagonal elements as an assumption instead. That's what I'm testing below:

 Clear[h];
 mat =
 Table[If[i <= j, h[i, j], Conjugate[h[j, i]]], {i, 3}, {j, 3}];
 MatrixForm[mat]

> $\left(
\begin{array}{ccc}
 h(1,1) & h(1,2) & h(1,3) \\
 h(1,2)^* & h(2,2) & h(2,3) \\
 h(1,3)^* & h(2,3)^* & h(3,3) \\
\end{array}
\right)$

The documentation states that `HermitianMatrixQ[mat]` is "effectively" equivalent to `ConjugateTranspose[mat] == mat`. Let's see if that is true:
 
 Assuming[{Apply[And, Map[# ∈ Reals &, Diagonal[mat]]]}, 
 Simplify[ConjugateTranspose[mat] == mat]]
 
 (* ==> True *)
 
 Assuming[{Apply[And, 
 Map[# ∈ Reals &, Diagonal[mat]]]}, 
 Simplify[HermitianMatrixQ[mat]]]
 
 (* ==> False *)

It is not the same. So it may be that the problems of the OP have to do with this inconsistency. My suggestion therefore would be to **avoid** using `HermitianMatrixQ` as a test, and use the first variant instead.

**Edit**

Since `HermitianMatrixQ` appears to be used internally, we're stuck with it and need to follow Heike's answer. 

The key word in the documentation is that the matrix passed to `HermitianMatrixQ` must be **explicitly** hermitian. This means that although it does evaluate its arguments, it doesn't evaluate properly with `$Assumptions` when attempting to `Simplify`. That appears to severely limit the extent to which one can do symbolic matrix manipulations. I just checked that the same behavior also happens for `SymmetricMatrixQ`. 

To me this looks like an inconsistent behavior, but legalistically speaking one may not be able to call it a bug because of the word _"effectively"_... 

I wonder if anyone has additional insight as to why this is happening.

 [1]: http://reference.wolfram.com/mathematica/ref/HermitianMatrixQ.html