Start by counting the number of ways to color the triangle. If you have $n$ colors available, you have $n$ choices for the $4$-way vertex, $n-1$ for the one above it, and $n-2$ choices for the third. Think about how many choices you have for each of the others. You will get a $9^{\text{th}}$ degree polynomial in $n$.
Your mistake is: When coloring $B$ you don't necessarily have $2$ ways. If you have chosen $A\mapsto f$ then you still have three ways for $B$. Similarly at later stages.
We may assume $E\mapsto e$, $F\mapsto f$, $G\mapsto g$, $H\mapsto h$. The vertices $A$ and $C$ can then be colored independently in $3$ ways each. Thereby four different types emerge, each of which leads to a characteristic number of possible continuations. The types are:
Type $1$: Both $A$ and $C$ are colored $e$ or $h$. There is $1$ coloring of this type: $A\mapsto h$, $C\mapsto e$. This enforces $B\mapsto g$, $D\mapsto f$. Makes $1$ in total.
Type $2$: One of $A$ and $C$ is colored $e$ or $h$, and the other $f$ or $g$. There are $4$ colorings of this type. Assume $A\mapsto h$, $C\mapsto f$. This allows of $B\mapsto\{e,g\}$ and enforces $D\mapsto e$. Makes $8$ in total.
Type $3$: $A$ and $C$ are differently colored $f$ or $g$. There are $2$ colorings of this type. This allows of $B\mapsto\{e,h\}$, $D\mapsto\{e,h\}$. Makes $8$ in total.
Type $4$: $A$ and $C$ are equally colored $f$ or $g$. There are $2$ colorings of this type. Assume $A\mapsto f$, $C\mapsto f$. This allows of $B\mapsto\{e,g,h\}$, $D\mapsto\{e,h\}$. Makes $12$ in total.
It follows that there are $29$ colorings of the eight vertices, up to a permutation of the colors. The grand total then is $29\cdot24=696$.
Best Answer
There are $n^4$ ways to assign colors to the vertices, without regards to neighboring vertices being different. The graph has five edges, call them $e_1,\dots,e_5$. For each $i\in \{1,\dots,5\}$, let $C_i$ be the set of colorings where both endpoints of $e_i$ are the same color. Then the number of proper colorings is $$ n^4-|C_1\cup \dots \cup C_5|. $$ You can now directly apply the principle of inclusion-exclusion to this expression, resulting in $$ n^4-|C_1|-|C_2|-\dots-|C_5|\\ +|C_1C_2|+|C_1C_3|+\dots+|C_4C_5|\\ -|C_1C_2C_3|-\dots-|C_3C_4C_5|\\ +|C_1C_2C_3C_4|+\dots+|C_2C_3C_4C_5|\\ -|C_1C_2C_3C_4C_5| $$ You then just need to work through all of those intersections. Here is a semi-thorough sketch.
It is not hard to show $|C_1|=\dots=|C_5|=n^3$, resulting in the $-5n^3$ term.
The pairwise intersections contribute $10n^2$. Suppose that $e_1,e_2,e_3,e_4$ are the edges of the square, numbered in anti-clockwise order with $e_1$ on top, and $e_5$ is the diagonal.
You can show that $|C_1C_2|=n^2$, since to color something in $C_1$ and $C_2$, the three vertices spanned by $e_1$ and $e_2$ must all be the same color, while the remaining vertex can be colored freely. The same applies to $|C_iC_j|$ whenever $e_i$ and $e_j$ share an endpoint.
We also have $|C_1C_3|=|C_2C_4|=n^2$. This time, colorings in $C_1C_3$ require making two choices, one for the two endpoints of $e_1$, the other for the two endpoints of $e_3$.
For the triple-wise intersections, the contribution will be $-2n^2-8n$. Here, there are two cases, based on whether the three selected edges span the entire graph, or whether they make a triangle. For example, $|C_1C_2C_3|=n$, but $|C_2C_3C_5|=n^2$.
The four-way intersections contribute $+5n$, since any choice of four edges will span the entire graph. Similarly, $|C_1\dots C_5|=n$.
Adding these all up leads to $n^4-5n^3+8n^2-4n$.