I met Neil of "Scotland from the Cape" in Windhoek in February 09 just as he had given up on getting an Angola visa and had arranged to ship his bike to Ghana along with two other guys. Yeah, that sucked big time.
But two others riders, from Poland, got Angola visas in Namibia about two months later. Read about that here Singapore2Poland
For a contact in Angola who will provide a letter of invitation you could try Nancy's English School e Hospederia in Benguela. Nancy is an American and very helpful and runs a decent hotel. I stayed with her. Can't find an email on the Web but her number is in the Lonely Planet guide -- 244 923 594 093.
Good luck. Hopefully the Namibia-to-Angola visa situation has improved by now but who knows.