This is really a glorified comment, but the formatting in answer boxes is easier (and I think the information deserves greater visibility). Apologies to the OP if he already knew this.
From Katznelson's introduction to Harmonic Analysis (the Dover version, 2nd corrected edition). Everything takes place on the circle ${\bf T}$.
Chapter IV, Theorem 2.4.
(a) There exists a continuous function $f$ such that for all $p<2$, $\sum \vert\widehat{f}(n)\vert^p = \infty$.
(b) [paraphrased by YC] There exists a sequence $(a_n)_{n\in{\bf Z}}$ which belongs to $\ell^p$ for every $p>2$, but which is not the Fourier series of any finite Borel measure on ${\bf T}$.
Quite a lot has been done, in the classical days of the subject, on how smoothness/Hölder conditions on a function are reflected in the rate at which its Fourier series decays: see Chapter I, Section 4 of the same book.
On a positive note, if the Fourier series is lacunary, then it is the Fourier series of a continuous function iff it belongs to $\ell^1$. (Chapter V, paragraph 1.4; this is sometimes stated as "lacunary sets are Sidon sets")
The circumstantial evidence, as I understand it, is that there is no way to characterize the Fourier series of continuous functions by means of a naive "sequence space" condition on the sequence. However, as Mike Jury has pointed out, one can use Fejer's theorem to get some kind of algorithm-flavoured criterion.
