I found the problem. The second mac's finder was not showing Airport Extreme neither. However, there was an item named 'All...' under Shared. After clicking that AE appeared, after clicking that and entering the password, the HDD connected to the AE was accessible. From then on Time Machine DID list the external HDD connected to the AE as a backup disk.
Now that I've been reading thougn it seems Apple does not wants us to use Time Machine with external HDDs. This is very bad unfortunately; if I'd known this I would have bought Time Capsule instead of Airport Express. The only reason I didn't was because I already have external HDDs at home wanted to save some bucks.
However, what puzzles me is that, Time Capsule IS also a backup over wifi, which is essentially the same as having an AE with and HDD.
Well, will see how it goes.
Thanks for the help.