Immigration authorities generally cite Matter of Ajami, 22 I&N Dec. 949 (BIA 1999) (Michigan conviction for aggravated stalking, in violation of M.C.L.A. 750.411i is a crime involving moral turpitude), for the proposition that threatening another is a CMT. Ajami may be not be the end of the issue, however, since that case involved a pattern of behavior, rather than a single instance of issuing a threat. Depending upon the statute at issue, the conviction may not involve an intent to carry out the threat or the intent that the threat was believed. Even though for it to be a true threat it must be normally one that a reasonable person would fear was real, it could be possible, depending on the elements of the statute, for the mens rea as to the outcome of the threat (that it would reasonably be believed) to be as low as negligence.

Since an intentional threat that is not intended to be carried out and not intended to be believed can still be a threat if a reasonable person would believe it, you might not have to prove the accused intended or thought it was believable, to be convicted, as long as they were careless to a criminal extent, i.e negligent as to the result of the threat. This arguably detracts from the evil nature of the offense.
The nature of the threat may also be an issue, such as a threat to commit a property crime (graffiti), or to damage the other persons reputation.

There may also be freedom of speech issues:

The First Amendment, applicable to the States through the Fourteenth Amendment, provides that Congress shall make no law ... abridging the freedom of speech. Virginia v. Black, 538 U.S. 343, 358, 123 S.Ct. 1536, 155 L.Ed.2d 535 (2003). While the scope of the First Amendment is broad, it does not extend to unprotected speech. Kilburn, 151 Wash.2d at 42"43, 84 P.3d 1215.

True threats occupy one category of unprotected speech. Id. at 43, 84 P.3d 1215. A true threat is a statement made in a context or under such circumstances wherein a reasonable person would foresee that the statement would be interpreted as a serious expression of intention to inflict bodily harm upon or to take the life of another person. Id. (internal punctuation and quotation marks omitted) (quoting State v. Williams, 144 Wash.2d 197, 208"09, 26 P.3d 890 (2001)). . . . The speaker of a true threat need not actually intend to carry it out. Id. at 46, 84 P.3d 1215. It is enough that a reasonable speaker would foresee that the threat would be considered serious.

Importantly, only threats that are true may be proscribed. The First Amendment prohibits the State from criminalizing communications that bear the wording of threats but which are in fact merely jokes, idle talk, or hyperbole. Id. at 43, 84 P.3d 1215. We recently interpreted the bomb threat statute, RCW 9.61.160, to reach only true threats in order to save it from a constitutional challenge. State v. Johnston, 156 Wash.2d 355, 364, 127 P.3d 707 (2006). We adhere to this principle and construe the threats-to-kill provision of RCW 9A.46.020 to the same effect.

State v. Schaler,169 Wash.2d 274, 283-284, 236 P.3d 858, 862-863 (Wash. 2010). See also Fernandez-Ruiz v. Gonzalez, 468 F.3d 1159 (9th Cir. 2006) (placing another person in reasonable apprehension of physical injury is not a CMT). Thanks to Jonathan Moore.