The connection wizard should automatically detect that it is being connected to a new machine and it adds some additional questions in to the wizard.
Did you (as when you first install) follow all the steps - ie install AS, only connect the cradle when it tells you, only connect the Axim when it tells you etc.
A lot of people forget to do this and connect the cradle before installing the software
Also when not connected can you open AS on your PC and go to FILE> Delete Partnership.
Delete the partnership and then put the Axim in the cradle.
Any joy?