Non-examples of model structures, that fail for subtle/surprising reasons?
Here is a classical example.
Let CDGA be the category of commutative differential graded algebras over a fixed ground field k of characteristic $p$. Weak equivalences are quasi-isomorphisms, fibrations are levelwise surjections. These would determine the others, but cofibrations are essentially generated by maps $A \rightarrow B$ such that on the level of the underlying DGA, $B$ is a polynomial algebra over $A$ on a generator $x$ whose boundary is in $A$.
CDGA is complete and cocomplete, satisfies the $2$-out-of-$3$ axiom, the retract axiom, satisfies lifting, and a general map can be factored into a cofibration followed by an acyclic fibration by the small object argument.
However, you don't have factorizations into acyclic cofibrations followed by fibrations, because of the following.
Suppose $A \rightarrow B$ is a map of commutative DGAs which is a fibration in the above sense. Then for any element $[x]$ in the (co)homology of $B$ in even degree, the $p$-th power $[x]^p$ is in the image of the cohomology of $A$. In fact, pick any representing cycle $x \in B$ and choose a lift $y \in A$. Then the boundary of $y^p$ is $py^{p-1} = 0$ by the Leibniz rule, so $[y^p]$ is a lift of $[x]^p$ to the (co)homology of $A$.
(As a result, there are a lot of other "homotopical" constructions, such as homotopy pullbacks, that are forced to throw you out of the category of commutative DGAs into the category of $E_\infty$ DGAs.)
Nothing goes wrong in characteristic zero.
I like the following example because it is very close to the origins of homotopy theory (and also because I worked on it at the beginning of my career): proper homotopy theory. Objects are topological spaces, maps are proper maps, one can define proper homotopies via cylinders in the usual way, weak equivalences are proper homotopy equivalences, and cofibrations are proper maps satisfying the homotopy extension property. The 'cofibrant' part works as in a model category, this is a cofibration category, but there are very few fibrations. Moreover, the category is not complete, it doesn't even have a final object. This is because the map to a point $X\rightarrow *$ is not proper unless $X$ is compact. Proper homotopy theory is however very much developed on its own, and has been applied in many contexts.
There is a whole slew of examples given by the $J$-semi model structures which arise in the study of operads and algebras over an operad. A $J$-semi model category satisfies most of the axioms of a model category, but two have to be tweaked. First, not all trivial cofibrations lift against fibrations; only those with cofibrant domain do. The lifting of cofibrations against trivial fibrations works as usual. Second, not all maps factor into a trivial cofibration followed by a fibration; only those maps with cofibrant domain do. The other factorization works fine.
These come up because without strong hypotheses on the underlying category $M$, one doesn't know that $Op(M)$ is a model category ($M$ needs to have a monoidal fibrant replacement functor and a commutative Hopf interval object, see e.g. the nLab) . But with very minimal hypotheses on $M$ (symmetric monoidal and cofibrantly generated suffice) you do get a $J$-semi model category. The concept of a $J$-semi model category--under a different name--appeared first in a preprint of Hovey called Monoidal Model Categories (Theorem 2.3), available from his website. This paper was a follow-up to the famous paper Algebras and Modules in Monoidal Model Categories, by Schwede and Shipley. Hovey was trying to figure out what could be said in the absence of the monoid axiom from that paper.
The best reference for $J$-semi model categories is Markus Spitzweck's Operads, Algebras and Modules in General Model Categories. This defines them more generally than Hovey and develops a theory which mimics that in Hovey's book on Model Categories. Corollary 8 of Spitzweck shows that Tyler's example is a $J$-semi model category which is not a model category. It proves in particular that if $M$ is a cofibrantly generated left proper model category with domains of the generating cofibrations cofibrant and cofibrant unit, then commutative monoids in $M$ form a $J$-semi model category. This paper also shows that if $O$ is an operad which is cofibrant in the projective model structure on collections, then algebras over $O$ and modules over a cofibrant $O$-algebra $A$ have $J$-semi model structures. Getting actual model structures rather than $J$-semi model structures requires more hypotheses on the underlying category $M$, and is part of my current thesis work.
Another example in the same style as $J$-semi model categories, but on the fibrant side, are the semimodel categories which appear in Clark Barwick's "On the Dreaded Right Bousfield Localization." A right semimodel category satisfies all the usual axioms, but factorizations into cofibrations followed by trivial fibrations and the lifting criterion for trivial fibrations only hold if the codomain is fibrant. A left semimodel category is a $J$-semi model category. Barwick proves that the right Bousfield localization of $M$ is a right semimodel categories, even if $M$ is not right proper. This gives many examples of right semimodel categories which are not model categories.
Here are a few other examples I've found of things which are not model categories.
In this paper of Schwede he mentions on page 22 that the category of commutative DFSPs is not a model category. A DFSP is a degreewise functor with smash product. They are models for brave new rings in $\Gamma$-spaces. The failure is because the $E_\infty$ structure on the cofibrant replacement $QS^0$ is not equivalent to a commutative simplicial monoid structure. Again, this example demonstrates the difference between $J$-semi model structures and model structures.
In this paper of Mandell he mentions on page 38 that this category $\mathcal{E}_{F_q}$ is not a model category, even though it has a homotopy category. It's the category of $E_\infty$ $F_q$ algebras. The failure is related to Tyler's example, but is different because the operad is cofibrant in this case.
In these notes of Bergner she mentions on page 16 that the category $SSet^{\Delta^{op}}_{disc}$ of Segal precategories does not have a model structure with cofibrations being monomorphisms and weak equivalences levelwise. She gives an example where factorization fails. This kind of failure of a model structure is also mentioned in recent work of Shipley and Hess. Again the issue is related to needing cofibrations to be monomorphisms.
Here are some examples of model categories which are not cofibrantly generated (since the last paragraph of the OP's question suggests these would also be of interest)
Hovey and Christiensen's paper "Quillen model structures for relative homological algebra" studies model structures on the category of unbounded chain complexes of $R$-modules and characterizes which are cofibrantly generated (including examples which are not).
Boris Chorny's "An example of a non-cofibrantly generated model category" gets such a model structure on diagrams in Top.
Adámek, Herrlich, Rosicky, and Tholen's "Weak Factorization Systems and Topological Functors" gets a model structure on the category of small categories which is not cofibrantly generated. It's the one coming from the weak factorization system (Full functors, Topological functors).
Isaksen's "A model structure on the category of pro-simplicial sets" is another non-cofibrantly generated model category.
Lack's "A 2-categories companion" proves that $Cat^{\mathcal{A}}$ for $\mathcal{A}=2$ is not cofibrantly generated.
This post of Emily Riehl's suggests that the injective model structure on diagrams might not be cofibrantly generated. I thought about how to find an example where I could prove it failed, but couldn't. I plan to ask my own MO question about this soon.
EDIT: The last example is cofibrantly generated, both on $Ch(R)$ (see Theorem 2.3.13 in Hovey's book) and on diagram categories $M^D$. Riehl was asking about $Ch(A)$ for an abelian category $A$ with enough injectives. There's potentially an example in that setting of a model category which is not cofibrantly generated, but it doesn't seem to be known. As for diagram categories, in order to know the injective model structure on $M^D$ exists you usually need to know $M$ is combinatorial (and $D$ is small, of course). In HTT, Lurie proves (A.2.8.2) that if $M$ is combinatorial then $M^D$ is combinatorial, so it's cofibrantly generated. Furthermore, $id:M^D_{inj} \stackrel{\to}{\gets} M^D_{proj}:id$ is a Quillen equivalence. I learned this from the nLab, but the proof is trivial once you know the statement because the maps in question are all defined levelwise, so it's just the fact that $id_M$ is a Quillen equivalence.
EDIT #2: In Chapter 4 of May and Sigurdsson's Parameterized Homotopy Theory another type of "almost model category" comes up. In particular, given a topological model category $C$ you can try to define an $h$-type model structure analogous to what is done for spaces. So a map is an $h$-fibration if it has CHP (i.e. the RLP with respect to $X\to Cyl(X)$ for all $X$), and is an $h$-cofibration if it has HEP (i.e. the LLP with respect to $Cocyl(X)\to X$ for all $X$). Say that $f$ is a strong $h$-fibration if it has the relative CHP, and a strong $h$-cofibration if it has the relative HEP. Then using $h$-fibrations and strong $h$-cofibrations OR using $h$-cofibrations and strong $h$-fibrations give two new structures which satisfy all the axioms for a model category except that the factorization axiom becomes
"Any map $f: X \to Y$ factors as $X \to Mf \to Y$ where the first map is a strong $h$-cofibration and the second has a section which is an $h$-acyclic strong $h$-cofibration, and $f$ factors as $X\to Nf \to Y$ where the first map is a strong $h$-fibration and the second has a section which is an $h$-acyclic strong $h$-fibration."
This is Theorem 4.3.1. Theorem 4.4.2 gives a hypothesis under which this almost model structure becomes a model structure. You need to know that given a chain of $h$-acyclic $h$-cofibrations $j_n:Z_n\to Z_{n+1}$ and given a compatible system $q_n:Z_n\to Y$ which gives $q:$colim $Z_n \to Y$ then colim $Nq_n \to Nq$ is an isomorphism in $C$. So the failure of these structures on $C$ to form a model structure has to do with the failure of this axiom, which I imagine is a bit surprising to those who don't work with model categories a lot.
EDIT (3/9/14): It appears I made a mistake in my earlier version of this answer (and in a recent edit), due to not fully understanding the notation in Markus Spitzweck's thesis. Corollary 8 which I discuss above in the struck out text is not actually about strictly commutative monoids and thus has nothing to do with Tyler's answer. Spitzweck uses the notation $Comm_C$ to denote algebras over a particular $E_\infty$ operad, and the $\Sigma$-cofibrancy of that operad assures us (by his Theorem 5) that algebras over the opeard have a semi-model structure. $Com$ is not $\Sigma$-cofibrant in general, and in positive characteristic, $CDGA(k)$ is not a semi-model category (I recently proved that if it were then in fact CDGA($k$) would be a (full) model category). Note that $Com$ is $\Sigma$-cofibrant in $Ch(k)$ if $k$ is a field of characteristic zero, because in this setting all symmetric sequences are projectively cofibrant (I learned this from recent papers of John Harper). For non-zero characteristic it should be easy to construct examples which show that $Com$ is not $\Sigma$-cofibrant.