Link Ubuntu server to GoDaddy domain

Just to let you know, there are records, and they are propagating. Firstly the domain registration and delegation of the nameservers is OK:

[madhatta@www ~]$ whois alexchen.co @whois.nic.co
[Querying whois.nic.co]
[whois.nic.co]
Domain Name:                                 ALEXCHEN.CO
[...]
Name Server:                                 NS1.DREAMHOST.COM
Name Server:                                 NS2.DREAMHOST.COM
Name Server:                                 NS3.DREAMHOST.COM

Secondly, at least one nameserver at dreamhost is serving an A record for you:

[madhatta@www ~]$ dig alexchen.co @ns1.dreamhost.com
[...]
;; ANSWER SECTION:
alexchen.co.        14400   IN  A   173.236.220.66

So that much is working. It seems to me that if you put up the alexchen.co site on 173.236.220.66, and the webserver there is configured to serve it, everything should work. I must also add that, when I point a web browser at alexchen.co, I see nice, shiny wordpress site looking back at me. What do you see?

What interests me is that your old domain is on a different address:

[madhatta@kiev systems]$ dig alexchen.info
[...]
;; ANSWER SECTION:
alexchen.info.      14400   IN  A   173.236.217.156

I don't know the details of what you're trying to do, but is that what you expected? If so, can you confirm that you're still having the problems, and they weren't - as others have sensibly suggested - propagation delays?

You say you're on ubuntu, which should have both the tools I've used above, dig and whois; they're invaluable for trying to debug DNS issues.

OK, first things first: Go to you local book store (or library if it's got a decent selection of technical books) and pick up a copy of DNS & BIND - any edition will be sufficient, though if you're buying one buy the latest. Then read this book cover to cover, or at least read through chapters 1, 2, 3, 5 and 6.

I am absolutely serious about this - If you try to set up DNS without a solid understanding of what's going on you are in for a wold of pain, suffering and mysterious breakage. Spending a day with a good book on DNS will pay for itself the first time you have a problem.

Now to actually answer your questions :-)

Re: the issue of being flagged as spam: Hosting your own DNS may or may not solve the problem of your system being flagged as a spam source -- The question you haven't asked/answered is WHY you are being flagged as a spam source (Is it your IP, the lack of SPF records, a bad reverse-DNS entry, or is your server perhaps misconfigured and really being used to send spam?).
You need to answer that question first, then pursue solutions based on what you discover.

If after investigating the incident problem you still want to host your own DNS (either as part of a solution to the incident problem, or just for the experience) . . .

I'm pretty sure the error you're getting from GoDaddy is their way of saying you're missing glue records -- In plain English "You want us to use ns1.xxx.com as a nameserver for xxx.com, but we have no way of finding that server".

Prior to using a host within in your own zone as an NS you need to create glue records for it. You can do this in GoDaddy's domain manager's "Host" box -- Add a domain host for each NS you want to use, and the system should then let you specify those hosts as the domain's nameservers.

BIG IMPORTANT WARNING
Before you flip the switch check, double-check and triple-check that the servers you're about to set as the authoritative NS are working properly (they resolve all the names they're supposed to resolve, you can query them from a machine off your network, etc.).

Many admins (probably every one who has ever set up DNS) probably has a horror story about screwing up and knocking their domain off the internet for a while -- Don't be a statistic like the rest of us :-)