One I like very much is 
> [Can we color $\mathbb Z^+$ with $n$ colors such that $a, 2a, \dots, na$ all have different colors for all $a$?][1]

Among the failed proposed attempts, the ones that appeared most promising were in essence group- or number-theoretic, for instance the question of whether the partial graph of multiplication $$\{(a,b,c)\in\{1,\dots,n\}^3\mid ab=c\}$$ could be extended to a group operation on $\{1,\dots,n\}$, with the first counterexample being $n=195$. 


  [1]: http://mathoverflow.net/q/26358/6085