Exchange 2007 550 5.1.1 Resolver

The problem;
 When some users try to sending emails or calendar requests they get the following NDR returned to them.

Diagnostic information for administrators:

Generating server: 64srv2003.Domain.co.uk
IMCEAEX_O=Domain_OU=First+20administrative+20group_cn=Recipients_cn=am05379903@Domain.co.uk
#550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##
Original message headers:
Received: from 64srv2003.Domain.co.uk ([10.0.1.102]) by
 64srv2003.Domain.co.uk ([10.0.1.102]) with mapi; Tue, 21 Oct 2008
 09:31:34 +0100
Content-Type: application/ms-tnef; name="winmail.dat"
Content-Transfer-Encoding: binary
From: Alastair Moir <alastair@Domain.com>
To: 'Alastair Moir'
      <IMCEAEX-_O=Domain_OU=First+20administrative+20group_cn=Recipients_cn=am05379903@Domain.co.uk>,
      Julian Cassell <Julian@Domain.com>, Toby Knott <toby@Domain.com>
Date: Tue, 21 Oct 2008 09:31:33 +0100
Subject: JC: TK: Pegasus Training
Thread-Topic: JC: TK: Pegasus Training
Thread-Index: AckwXLteR9xDKtvbRCaqlFDiTECVjAC+rGTw
Message-ID: <B46DE97149E9AD4ABBB2D3D7A78C819D0170A4920F@64srv2003.Domain.co.uk>
Accept-Language: en-US, en-GB
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator: <B46DE97149E9AD4ABBB2D3D7A78C819D0170A4920F@64srv2003.Domain.co.uk>
MIME-Version: 1.0

History of the network;
We had a exchange 2003 server and joined a Exchange 2007 Server to the Organization. This caused a lot of Legacy problems when the 2003 server was removed. The decision was made to backup the users data(mailboxs) and Public folder to PST files and remove Exchange from the Domain completely. Once this was done we installed a fresh copy of Exchange 2007 onto our server. All of the user mailboxes and Distribution List were created without a problem. The data was imported into the relevant mailboxes and the Public Folder recreated.
Now at this point we did have a problem when trying to edit old appointments that have been created via emailed requests. But I believe that this is because the users that created the appointments are no long there (as the exchange server has been completely restored).
We also had an instance where exchange creates the default email address as alais@Domain.co.uk. I have had to change this for some users as we wanted their email format to be different. It just so happens that the user who had the above NDR was one of the users that default email address was changed.
So, my thoughts are theres a problem with GAL or something to do with the X500 address not matching the new default email address???

Any suggestions or thoughts would be gladly received.
Regards,