In my situation, being or not in the same workgroup does not make a difference.
In any case here are some detailed descriptions of what happens. As I wrote in comment 8, I have a virtual machine running hardy-beta, which is in the same worgroup (or Domain) of all other network machines. This is a large network, with mostly windows clients, but also with several MacOsX and linux boxes. All linux boxes were joined to the ADS domain with the command: 'net ads join'. The relative smb.conf file is like this:

[global]
        workgroup = LAB
        realm = XXXLAB.IT
        netbios name = %h
        server string = %h (Samba %v, Ubuntu)
        security = ADS
        password server = dhcserv1.xxxlab.it
        username map = /etc/samba/domain_users.map
        restrict anonymous = 2
        client NTLMv2 auth = Yes
        client lanman auth = No
        client plaintext auth = No
        log file = /var/log/samba/log.%m
        os level = 0
        preferred master = No
        local master = No
        domain master = No
        idmap domains = LAB
        idmap config LAB: default = yes
        idmap config LAB: backend = rid
        idmap config LAB: range = 100000-1000000
        template shell = /bin/bash
        winbind enum users = Yes
        winbind enum groups = Yes
        winbind use default domain = Yes
        winbind offline logon = Yes
        invalid users = root


Case 1 ---------------------------------------------------------------------------------
Browsing from hardy-beta a machine running ubuntu-gutsy server.

In a terminal window:

renbag@vm-hardy:~$ smbclient -L gutsy-server
Password: (password inserted here)
Domain=[LAB] OS=[Unix] Server=[Samba 3.0.26a]

	Sharename       Type      Comment
	---------       ----      -------
	IPC$            IPC       IPC Service (gutsy-server (Samba 3.0.26a, Ubuntu))
	share           Disk      gutsy-server_share
Domain=[LAB] OS=[Unix] Server=[Samba 3.0.26a]

	Server               Comment
	---------            -------
	gutsy-server         gutsy-server (Samba 3.0.26a, Ubuntu)

	Workgroup            Master
	---------            -------
	LAB

In Nautilus:

Open Network --> Double-click on the 'LAB' icon (Domain) --> All machines are displayed;
Double-click on the 'gutsy-server' icon --> after a while, Nautilus returns '0 objects', without asking for a password;
Insert the full address (smb://gutsy-server/share) --> a password is requested and the share content is displayed.


Case 2 ---------------------------------------------------------------------------------
Browsing from hardy-beta a machine running Windows XP

In a terminal window:

renbag@vm-hardy:~$ smbclient -L XP-ACQ
Password: (password inserted here)
Domain=[LAB] OS=[Windows 5.1] Server=[Windows 2000 LAN Manager]

	Sharename       Type      Comment
	---------       ----      -------
	IPC$            IPC       Remote IPC
	Data            Disk      
	ADMIN$          Disk      Remote Admin
	C$              Disk      Default share
Domain=[LAB] OS=[Windows 5.1] Server=[Windows 2000 LAN Manager]

	Server               Comment
	---------            -------

	Workgroup            Master
	---------            -------

In Nautilus:

Same behaviour as in case 1.
smb://XP-ACQ --> '0 objects';
smb://XP-ACQ/Data --> content displayed after password.


Case 3 ---------------------------------------------------------------------------------
Browsing from hardy-beta a machine running Windows 2000

In a terminal window:

renbag@vm-hardy:~$ smbclient -L TF-2000
Password: (password inserted here)
Domain=[LAB] OS=[Windows 5.0] Server=[Windows 2000 LAN Manager]

	Sharename       Type      Comment
	---------       ----      -------      
	IPC$            IPC       Remote IPC    
	ADMIN$          Disk      Remote Admin
	C$              Disk      Default share
	Data            Disk        
Domain=[LAB] OS=[Windows 5.0] Server=[Windows 2000 LAN Manager]

	Server               Comment
	---------            -------

	Workgroup            Master
	---------            -------

In Nautilus:

Open Network --> Double-click on the 'LAB' icon (Domain) --> All machines are displayed;
Double-click on the 'TF-2000' icon --> All the shared folders are displayed, without asking for a password;
Double-click on the 'Data' folder icon --> a password is requested and the content is displayed.
(This is the correct and the expected behaviour).


I want to stress again that in ubuntu-gutsy boxes, with exactly the same smb.conf configuration, I never observed Nautilus return '0 objects' as in case 1 and 2.
Such a behaviour in hardy will make a normal user think that browsing a samba network, in a situation similar to the one described here, does not work at all, and so I think that this bug should gain a higher priority.
Please let me know if there is other I can do to produce more informations.