Who understands Statsforvaltningen and SKAT and can help?

Hey there. I'm Luke and I moved to Copenhagen in mid December. I live with my girlfriend (who is Danish) in north-west Copenhagen and I'm enjoying life here so far. I'm hoping somebody who has been through the same (and what seems like endless) task of registering can offer me some help and guidance with this rather complicated system.
I arrived at Statsforvaltningen the day after I touched down in Denmark. The person I spoke to told me that I am unable to register because I don't have a job contract, etc. Fair enough. Thankfully within 3 weeks I had a job interview and a job offer. The boss understood that it will take a short while to get a CPR number and the like sorted and wants me to start at the beginning of February. Obtaining a CPR number quickly is a priority as I will be working in Copenhagen Airport and need a security check to get an airport I.D card. This can apparently take up to two weeks. The manager wrote on my job contract that I will be starting on the 14th of February (the only reason I can think he done this is to allow time for me to be processed and put on the system).
So I took the job contract and my completed forms to Statsforvaltningen. The worker this time told me that I am 'too early' to be registered as I will be 'free in the system' until the 14th, where on the contract says I'm due to start working. She then kindly photocopied my passport and handed me a printed map of the SKAT office in Sluseholmen(sp?) and a TAX form to fill out. She told me that I can register for a tax card and a CPR number there. Very strange.
After the weekend I went to the SKAT office and spoke to someone who sounded like they knew what they were doing. He flicked through my form, took a photocopy of my contract and my passport and told me to relax and wait for the tax card (which he briefly explained would contain a CPR number), and that it should arrive within 10 working days.
Now my question to all the expats who read this is: did anyone have to go through this process and does it sound normal? The manager has been very patient so far and I don't want him to feel like I'm taking liberties. I respect that he could easily tap in the CPR number of a Dane or someone else who is fully registered here and is just as qualified, so I don't want him to lose interest. Tomorrow (Monday) will be the 6th working day I have been waiting eagerly for the arrival of my letter from SKAT. But because of all the let downs at Statsforvaltningen, Borgerservice, telephone calls to the Danish Immigration Service and previous calls to SKAT it seems I am being led on one giant goose chase. I stand to lose a lot because of something I am not even in control of. I really hope the application I sent off at the SKAT office is my ticket to start working and kick starting my life here. Also, I'm going to call the manager as soon / if I get the CPR number. Will it have activated and be on record as soon as I receive it? I think I have to take a CPR number to somewhere to register for a doctor and dentist and get the yellow card and I'm worrying I won't be able to use it (I think I'm being sent a tax card in the mail) but I hope this isn't the case. I can't afford to wait any longer!
I'm quite a mentally strong person and I believe persistence has got me this far. I can't imagine what it is like for people who don't speak English or Danish fluently moving here, being led from place to place. Coming from a fellow EU country this is quite a shock to me. In the UK it is so easy for foreign nationals to start work and I thought this welcoming attitude towards foreigners to work spanned the EU.
Sorry about the incoherent ramble. It's quite late and I'm tired.

If you have come this far then thanks for reading. I hope someone can shed some light on this!
I

It sounds very normal what you are going through. I went through the same thing when I moved to Sweden -- like in the US, you don't exist without a social security number. It sounds like you have taken all the right steps and now it is just a matter of being patient for the 10 days to pass and your number arrives. The rest should be relatively easy. The hard part was getting the job offer. Things like the yellow card should be easy. One thing to do while you're waiting is to pick out a doctor that is convenient and perhaps recommended by a friend, since it costs about 150DKK to change your primary care physician.
So take it easy and enjoy the time you have prior to starting to work at CPH!
Hope that helps!

Ive been here 5 years. Originally from Ireland. And I have been through HELL with the Statsforvaltning here. You have 3 months from arrival to find a job and register. Yeah, if you dont speak Danish good luck with that! You were very lucky to find a job in 3 weeks. I dont know how you did it. Normal procedure is go to statsforvaltning and register. Can only do this if you have a job, or more than 50.000 dkk in bank. In other words you must have money or the means to earn money. They dont care about anything else. Within 2 weeks you should get (If you are an EU citizen) a registration document from Statsforvaltning. Take this to your local Borgerservice and within a couple more weeks you should get your yellow health card with your address (you must have an address or you cannot register) and doctors address and phone number on it. Thats the theory. I was registered for years but then lost my job. After living on my own money for a year until it was all gone I made the stupid mistake of asking the Kommune for financial help. Not only did they not help me they told me to get the hell out of denmark. Had to go back to Statsforvaltning and re-register as self-employed. Process took 4 months. They are not friendly or helpful in any way. Dont ever want to go through that again. One question, how did you get job at airport? I tried that. I understand all danish now and can speak, but not fluently. Got to be able to speak fluently to get any job at airport. Even just baggage handling. I like denmark a lot but it is one of the most difficult of EU countries to live in for foreigners. Its hard to learn the language. Hard to find a job, hard to find a place to live, 50% tax, and the cost of living is the highest Ive ever seen. Also, being an EU citizen doesnt seem to give you any benefits at all, as compared to non-EU citizens.