It sounds like you're saying that you need/want to BOB to be cloned to the new hardware, and then you want the new hardware to even have the name BOB instead of its current name, FRED.
You have a lot of options here, and it all really depends on what your needs are. If BOB is just acting a SQL Express server, then it would probably be easiest to install Windows on FRED, then install SQL Server, and then detach and copy the databases from BOB to FRED, or backup the databases on BOB and restore them to FRED. Once you have removed BOB from the domain, it would be simple to just keep FRED as is without renaming it to BOB, and simply join FRED to the domain. However, if it has to be renamed to BOB, then you would need to go into Active Directory and either delete the machine account for BOB, or it would probably suffice to simply reset the machine account for BOB. After you do this, you'll be able rename FRED to BOB, and then you can join the new BOB to the domain.
If you have a lot more going on with BOB than just SQL Express, and you really feel that you need to clone it exactly there are many ways to do this without using Backup Exec, and many of them would probably be better or simpler ways. However, if you're going to use Backup Exec to do this in the way that was outlined in the instructions on the link you provided, then yes, your best bet is to remove the original BOB from the domain and delete or reset the machine account so that you can add the new BOB (FRED) to the domain. Once you have the new machine, BOB, on the domain, you can begin the restore process as described.