Here is a case where it is non-Abelian. I use $K$ of class number 3. If I use the Gross curve, it is Abelian. If I twist in $Q(\sqrt{-15})$, it is Abelian for every one I tried, maybe because it is one class per genus. My comments are not from an expert.
> K<s>:=QuadraticField(-23);
> jinv:=jInvariant((1+Sqrt(RealField(200)!-23))/2);
> jrel:=PowerRelation(jinv,3 : Al:="LLL");
> Kj<j>:=ext<K|jrel>;
> E:=EllipticCurve([-3*j/(j-1728),-2*j/(j-1728)]);
> HasComplexMultiplication(E);
true -23
> c4, c6 := Explode(cInvariants(E)); // random twist with this j
> f:=Polynomial([-c6/864,-c4/48,0,1]);
> poly:=DivisionPolynomial(E,3); // Linear x Linear x Quadratic
> R:=Roots(poly);
> Kj2:=ext<Kj|Polynomial([-Evaluate(f,R[1][1]),0,1])>;
> KK:=ext<Kj2|Polynomial([-Evaluate(f,R[2][1]),0,1])>;
> assert #DivisionPoints(ChangeRing(E,KK)!0,3) eq 3^2; // all E[3] here
> f:=Factorization(ChangeRing(DefiningPolynomial(AbsoluteField(KK)),K))[1][1];
> GaloisGroup(f); /* not immediate to compute */
Permutation group acting on a set of cardinality 12
Order = 48 = 2^4 * 3
> IsAbelian($1);
false
This group has $A_4$ and $Z_2^4$ as normal subgroups, but I don't know it's name if any.
PS. 5-torsion is too long to compute most often.
There is a formula that works in all degrees, not just imaginary quadratic. In a global field $K$, let $O$ be integral over ${\mathbf Z}$ or ${\mathbf F}[t]$ (${\mathbf F}$ a finite field) and be "big", i.e., it has fraction field $K$. Let $\mathfrak c$ be the conductor ideal of $O$ in its integral closure $R$. Then
$$h(O) = \frac{h(R)}{[R^\times:O^\times]}\frac{\varphi_{R}({\mathfrak c})}{\varphi_O(\mathfrak c)},$$
where $\varphi_O(\mathfrak c)$ is the number of units in $O/\mathfrak c$ and $\varphi_R(\mathfrak c)$ is the number of units in $R/\mathfrak c$. This is derived in Neukirch's alg. number theory book in the number field case, but it goes through to any one-dimensional Noetherian domain with a finite residue rings and a finite class group.
In the imag. quadratic case the unit index $[R^\times:O^\times]$ is 1 most of the time so you don't notice it.
Both $\varphi_R(\mathfrak c)$ and $\varphi_O(\mathfrak c)$ can be written in the form ${\text N}(\mathfrak c)\prod_{\mathfrak p \supset \mathfrak c}(1 - 1/{\text{N}(\mathfrak p)})$, where the ideal norm $\text N$ means the index in $R$ or $O$ and $\mathfrak p$ runs over primes in $R$ or $O$ for the two cases.
Best Answer
The only proof that I know that $(\mathbb{Z}/3\mathbb{Z})^3$ does not appear as the class group of a quadratic imaginary number field is by brute force search. Roughly, the idea is that since class numbers of quadratic fields increase with the discriminant, there are only finitely many such fields of any given class number. We can then enumerate all class groups of a given size, and check to see which class groups appear. Most recently, Watkins's computation of all quadratic imaginary number fields with class number up to 100 provides in particular a complete list of all class groups of order 27, and so by simple enumeration one can observer that $(\mathbb{Z}/3\mathbb{Z})^3$ does not appear. I should also mention in this regard the tremendous amount of data available in a recent article of Jacobson, Ramachandran, and Williams.
[Edit: As to another of your questions, the same technique shows 6 other class groups of order less than 100 do not appear as quadratic imaginary number fields, of orders 27,32,54,64,64,81,81 respectively, a fact I have stolen from https://math.stackexchange.com/a/11025/20762 (and now updated based on ABC's answer below).]
Lacking any particularly compelling arithmetic reasons which proscribe certain finite abelian groups from appearing as class groups of quadratic imaginary number fields, it's worth thinking about some heuristics. An argument of Soundararajan gives that, on average, the number of quadratic imaginary number fields of class number $p^n$ is roughly $p^n$ (or better, asymptotically between $p^n/n$ and $np^n$). On the other hand, the number of finite abelian groups of order $p^n$ is governed by the partition theory of $n$, and hence a standard asymptotic suggests there are $\frac{1}{4\sqrt{3}n}e^{\pi\sqrt{2n/3}}$ such groups. So roughly, there are increasingly more number fields of order $p^n$ than there are possible class groups of that size, so one might perhaps expect that (again, without any obvious arithemtical obstruction) that there are only finitely many examples like $(\mathbb{Z}/3\mathbb{Z})^3$ that do not appear, at least among $p$-groups (and especially for large $p$).
For real quadratic fields, there is no such bound pushing class numbers higher, and I can't see any reason not to expect every finite abelian group to appear as a class group of such a field. Of course, this result is nowhere near known.