Is there a polynomial $p(x)$ with integer coefficients, such that $p(a)=p(b)=p(c)=p(d)=4$ and $p(e) = 10$?

The problem is that in general the factors $(e-a), (e-b), (e-c), (e-d)$ are too large. But if we are careful, we can find examples, where this happens. For example, let $a=-1$, $b=-2$, $c=1$, $d=3$, $e=0$. Then $$ p(x)=(x+1)(x+2)(x-1)(x-3)+4 $$ has the values $p(-1)=p(-2)=p(1)=p(3)=4$ and $p(0)=10$.

Hint $\ $ The key to proving that many problems of this type are unsolvable is to simply apply the Factor Theorem $\rm\ x-y\ |\ p(x)-p(y)\ $ in $\rm\:\mathbb Z[x,y]\ $ for $\rm\:p(x)\in \mathbb Z[x]\:.\:$ Specializing $\rm\ x,y = m,n\in\mathbb Z\:$ we deduce that $\rm\: m-n\ |\ p(m)-p(n)\:$ in $\rm\:\mathbb Z\:.\:$

For example, considering the specific example in Jyrki's answer, since $\rm\:p(a) = 4\:$ for $\rm\:a\ne 0\:$ we infer that $\rm\: a-0\ |\ p(a)-p(0) = 4-10\:,\:$ i.e. $\rm\: a\:|\:6\:$ for $\rm\:a\ne 0\:.\:$ These severe arithmetic constraints are enough to resolve the problem in many cases. A long time ago I once crafted a problem based on this combined with Pick's theorem that went unsolved for a long time till someone noticed the trick (it was John H. Conway if memory serves correct - it's not easy to pull the wool over his eyes!)