Consider first all possible assignments of gifts, with as only condition that every person gets one gift. As you guessed this gives $5!=120$ possibilities. But among those there are possibilities where the first person gets her own gift. In fact the number of ways this arises is $4!=24$, since the remaining persons are exchanging gifts among each other, with no restrictions. Butit may also happen that the second person gets his own gift, again in $4!$ ways. Or the third, fourth or fifth person. Taking account of all these forbidden possibilities, there remain
$$
5!-4!-4!-4!-4!-4!= 5! -5\times 4! = 120 - 120 = 0\text{ possibilities.}
$$
That's right, we've eliminated as many solutions as there were, so there aren't any left. Or are there? Well we did genuinely rule out a possibility $120$ times, but fortunately they wern't all different. Consider a solution where the first two people get their own gift, but nobody else. That possibility would have been ruled out twice, but it was present only once, so we have to add it back once to get even. We also have to worry about solutions where $3$ people get their own gift, or $5$ (can you see why $4$ cannot happen?), and which would have to ne added back $2$ respectively $4$ times to get even.
We could count and each of these categories exactly, but that would hardly be simpler than the original problem; the philosophy of inclusion-exclusion is to first add back all solutions where the first two (and posibly more) get their own gift, and the same for the first and third, and so forth for all $\binom52=10$ pairs, and then start worrying about solutions where at least three people get their own gift. So we are adding back $10\times3!=60$ solutions here. So far we have computed
$$
5!-\binom51\times4!+\binom52\times3! = 5!-\frac{5!}{1!}+\frac{5!}{2!}
=5!(1-\frac11+\frac12)=60.
$$
We still need to worry about solutions where for instance the first three all get their own gift; such solutions have been counted once, then subtracted thrice, then added back $\binom32=3$ times, so all in all they have contributed once, although they are not legal solutions. Subtract off $\binom532!$ to get the solutions with exactly three gift returning to their sender accounted for properly.
You should see a pattern emerging here. By the time you get to accounting correctly even the possibility where everybody gets his/her own gift, you will have found the formula cited by vonbrand.
Suppose that the couples are Adam and Alice, Bob and Brenda, and Cathy and Charles.
If you just want the answer, you can calculate it online with Sage.
Open a notebook and type
D = Derangements(['A','A','B','B','C','C'])
D.cardinality()
and click "evaluate". The answer is 10.
You can, of course, choose different numbers of couples. You could also throw in singles, triples, etc.
If you want a list of them, then evaluate
D.list()
For instance, the entries in ['B','B','C','C','A','A'] are the first letter in the names drawn by Adam, Alice, Bob, Brenda, Cathy, and Charles respectively.
There are 8 ways to assign names to each arrangement, so the number of named permutations is 80. This result also follows from the formula in joriki's answer here. We have
$$\int_0^\infty (2-4x+x^2)^3 e^{-x}\,dx=80. $$
Update:
The Sage program that I suggested outputs a list of ten permutations, for example: ['B', 'B', 'C', 'C', 'A', 'A'].
What does this mean, and how come the answer to this question is sometimes 10 and sometimes 80?
First of all, we may as well suppose that the six people line up in alphabetical order to randomly choose a name.
We interpret ['B', 'B', 'C', 'C', 'A', 'A'] as follows:
$$\begin{array}{c||c|c|c|c|c|c}
\text{Chooser} &\text{Adam}&\text{Alice}&\text{Bob}&\text{Brenda}&\text{Cathy}&\text{Charles}\\ \hline
\text{First letter in}&\text{B}&\text{B}&\text{C}&\text{C}&\text{A}&\text{A}\\
\text{name chosen}\\
\end{array}$$
There are a total of ${6!\over 2!\,2!\,2!}=90$ possible permutations, and exactly 10 of them (including the one above)
correspond to the situation where nobody gets their own name or the name of their partner.
This is why the Sage program returns the answer 10.
Notice that the table above does not tell us what person chose which name, as
this information is not needed. All we need to know is that everyone chose a name
whose first letter differs from the first letter of their own name. The good permutations are
those with no $A$s in the first two spots, no $B$s in the second two spots, and no $C$s in the final two spots.
Suppose, though, that we want all that information anyway. One possible
outcome consistent with the example above is:
$$
\begin{array}{c||c|c|c|c|c|c}
\text{Chooser} &\text{Adam}&\text{Alice}& \text{Bob}& \text{Brenda}& \text{Cathy}& \text{Charles}\\ \hline
\text{Name chosen}&\text{Bob}&\text{Brenda}&\text{Charles}&\text{Cathy}&\text{Adam}&\text{Alice}\\
\end{array}
$$
There are a total of $6!=720$ "named" permutations and exactly 80 of them
correspond to the situation where nobody gets their own name or the name of their partner.
You see that every permutation of "first letters" corresponds to exactly $2!\times 2!\times 2!=8$
permutations of "names". That's because you could write, in either order, "Adam, Alice" or "Alice, Adam" for the $A$s. That is, you have two ways to write in the A-names. Similarly there are two ways to write in the B-names and two ways to write in the C-names. There are eight times as many named permutations as un-named permutations.
So what is the right answer: 10 or 80? Well, that's up to you. An argument could be made for either choice, but once you know one of them, it is easy to calculate the other one.
Best Answer
If each of you just draws a random name out of the hat, the probability that nobody gets their own or their partner's name is
$$\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%.$$
Thus, the expected number of times you'll need to repeat the process before getting "a solution that works" is $280/33 \approx 8.5$. This could get a bit tedious, but it'll hardly take "all year", at least unless you're both really slow and really unlucky with the draw.
Ps. I went and calculated the odds for other numbers of couples too:
If I'm not mistaken, as the number of couples involved tends to infinity, the probability of nobody getting their or their partner's name should tend towards the limit $e^{-2} \approx 13.5\%$, and thus the expected number of retries needed should tend towards $e^2 \approx 7.4$.