well, here's something that qualifies (it's only a slight improvement over previous answers for better rules-conformity.
weighing in at 67 chars:

print"$_ is married to $couples{$_}",chr 0x0a for sort keys%couples

just tr/0x0a/0x0d/ if your system uses that for newline. and, at 76 chars (ever so short of the limit...), the same code with microsoft newline:

print"$_ is married to $couples{$_}",chr 0x0d, chr 0x0a for sort keys%couples

~Cybercosis