The only example I know of a positive map which is not completely positive is the transpose map on $M_n(\mathbb{C})$. Of course, one can come up with minor perturbations of this (compose it with, or add it to, a completely positive map, etc). Are there other known examples?
7 Answers
In Theorem 4.6 of their paper
http://www.univie.ac.at/nuhagphp/bibtex/open_files/deha85_CanniereHaagerup.pdf
de Canni`ere and Haagerup construct an explicit sequence of finitely supported functions on the free group $\mathbb{F}_N$ ($N\geq 2$), defining positive multipliers of the reduced C*algebra $C^*_r(\mathbb{F}_N)$, and such that the corresponding sequence of multipliers converges strongly to the identity of $C^*_r(\mathbb{F}_N)$. As $C^*_r(\mathbb{F}_N)$ is nonnuclear, it does not have the completely positive approximation property, so only finitely many of these multipliers are completely positive.
First, let me recall some definitions to make sure I understand (at least the matrix version of) the question correctly. All of what I say below is based on Chapter 3 of the delightful book Positive Definite Matrices by R. Bhatia.
Let $\mathbb{M}_n$ denote the space of $n \times n$ complex matrices over $\mathbb{C}$, and let $\mathbb{M}_k(\mathbb{M}_n)$ denote the set of $k \times k$ block matrices, having elements of $\mathbb{M}_n$ as its blocks. I'll just speak of positive and completely positive maps, and not restrict to linear maps (yet).
Consider the map $\Phi_k: \mathbb{M}_k(\mathbb{M}_n) \to \mathbb{M}_k(\mathbb{M}_p)$, is induced by a positive map $\Phi: \mathbb{M}_n \to \mathbb{M}_p$, so that in particular for a $k\times k$ block matrix $A$, we have \begin{equation*} \Phi_k(A) := [\Phi(A_{ij})]. \end{equation*}
If $\Phi_k$ is a positive map for all $k=1,2,\ldots,$, then $\Phi$ is called a completely positive (CP) map. Notice that $k=1$ coincides with "ordinary" positive maps.
Now, with this definition, it is quick matter to construct maps that are positive but not CP, for example, say the map $X \mapsto X^{1}$ on positive matrices.
Additionally, if you are looking only at positive linear maps and and CP linear maps, then you can appeal to a theorem of Choi and Kraus that says that each CP map $\Phi$ must assume the representation $\Phi(A) = \sum_i V_i^*AV_i$, and you need only find a positive (linear) map that does not assume this representation.
Why the above should be true can also be seen from the following deeper observation. Suppose that every positive linear map $\Phi: \mathbb{M}_n \mathbb{M}_p$ could be written as $$\Phi(A) = \sum_i V_i^*AV_i + \sum_j V_j^*A^TV_j,$$ then it would follow that every real polynomial in $n$ variables that takes only nonnegative values is a sum of squares of real polynomials. But this claim was shown to be false by Hilbert.
Here's something neat: Here it is proved, by Sixia Yu, that in the finitedimensional case, any positive map that isn't completely positive can be written as the difference of two completely positive maps. The paper also considers a necessary and sufficient condition for a positive map to fail complete positivity (also in finite dimensions). This paper apparently provides a mechanism for generating examples answering your question in the finitedimensional case.

$\begingroup$ @Yemon: I don't see how your WLOG works. It seems to be saying that the algebra generated by any finite dimensional operator system is finite dimensional. Right? Surely this is not true, just take something in a free product. $\endgroup$ Feb 13, 2012 at 1:42

$\begingroup$ @Owen: ah yes, of course, a silly oversight on my part. [Erroneous comment deleted] $\endgroup$ Feb 13, 2012 at 7:46
A Jordan homomorphism between C*algebras is always positive, but it is completely positive only if it is a homomorphism. To get some examples, say $C_r^*(G)$ is the reduced C*algebra of a discrete group or groupoid $G$. Then the map $g\mapsto g^{1}$ (a generalized transpose) induces a Jordan homomorphism on $C_r^*(G)$ which is positive but not completely positive.
One example other than the transpose is Arveson's example of a noncontractive unital positive map (see Paulsen's book, Example 2.2). Since any unital completely positive map is contractive, Arveson's map cannot be completely positive. The example is like this: let $\mathcal{S}$ be the operator system $$ \mathcal{S}=\text{span}\{1, z, \bar{z} \} \subset C(\mathbb{T}), $$ and let $\phi:\mathcal{S}\to M_2(\mathbb{C})$ be given by $$ \phi(a+bz+c\bar{z})=\begin{bmatrix}a&2b\\ 2c& a\end{bmatrix}. $$
This example might not be satisfactory for some operator algebraists because it cannot be extended to an example with a C$^*$algebra domain. A way to produce examples between C$^*$algebras would be this: we use Choi's theorem that characterizes completely positive maps $\varphi:M_n(\mathbb{C})\to B(H)$. Choi's result asserts that $\varphi$ is completely positive if and only if the matrix $$ \left[\varphi(e_{kj})\right]\in M_n(B(H)) $$ is positive, where $\{e_{kj}:\ k,j=1,\ldots,n\}$ are the standard matrix units. The only caveat is that one needs to produce positive maps on the matrices by showing explicit computations on the matrix entries, and this might not be that easy. I'm familiar with examples on small operator systems, where positivity of the elements can be established with simpler formulas, but I cannot see right away a path to do this explicitly for full matrix algebras.
I know nothing but a quick google search gives http://www.quantiki.org/wiki/Separability_criteria where 2 other examples are given. Maybe somebody who knows more can flesh it out so I made this CW.
Continuation of the answer of Benjamin Steinberg; this paper gives a list of such known maps.
On the structure of entanglement witnesses and new class of positive indecomposable maps: by Dariusz Chruscinski and Andrzej Kossakowski; http://xxx.imsc.res.in/abs/quantph/0606211v1 and the journal version (if you want) is here.
It is slightly outdated but gives a good starting point. Not many classes of such maps are known in literature.