I think I have the same problem, and connecting with smbclient with debug on results in this answer (feisty has only share level security):

This is a (failed) connection FROM an Edgy machine TO Feisty share:

martin@minivanes:~$ smbclient -d 3 //feisty/samba
lp_load: refreshing parameters
Initialising global parameters
params.c:pm_process() - Processing configuration file "/etc/samba/smb.conf"
Processing section "[global]"
added interface ip=192.168.1.73 bcast=192.168.1.255 nmask=255.255.255.0
Client started (version 3.0.22).
resolve_lmhosts: Attempting lmhosts lookup for name feisty<0x20>
resolve_wins: Attempting wins lookup for name feisty<0x20>
resolve_wins: WINS server resolution selected and no WINS servers listed.
resolve_hosts: Attempting host lookup for name feisty<0x20>
name_resolve_bcast: Attempting broadcast lookup for name feisty<0x20>
Got a positive name query response from 192.168.1.22 ( 192.168.1.22 )
Connecting to 192.168.1.22 at port 445
Password:
Domain=[MSHOME] OS=[Unix] Server=[Samba 3.0.24]
resolve_lmhosts: Attempting lmhosts lookup for name feisty<0x20>
resolve_wins: Attempting wins lookup for name feisty<0x20>
resolve_wins: WINS server resolution selected and no WINS servers listed.
resolve_hosts: Attempting host lookup for name feisty<0x20>
name_resolve_bcast: Attempting broadcast lookup for name feisty<0x20>
Got a positive name query response from 192.168.1.22 ( 192.168.1.22 )
Connecting to 192.168.1.22 at port 445
dos_clean_name []
convert_string_allocate: Conversion error: Incomplete multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(��_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(�_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence(▒_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence)
convert_string_allocate: Conversion error: Incomplete multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(��_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(�_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence(▒_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence)
convert_string_internal: Conversion error: Incomplete multibyte sequence(���_)
convert_string_internal: Conversion error: Illegal multibyte sequence(���_)
convert_string_internal: Conversion error: Illegal multibyte sequence(��_)
convert_string_internal: Conversion error: Illegal multibyte sequence(�_)
convert_string_internal: Conversion error: Incomplete multibyte sequence(▒_)
convert_string_internal: Conversion error: Incomplete multibyte sequence)
resolve_lmhosts: Attempting lmhosts lookup for name ���_<0x20>
resolve_wins: Attempting wins lookup for name ���_<0x20>
resolve_wins: WINS server resolution selected and no WINS servers listed.
resolve_hosts: Attempting host lookup for name ���_<0x20>
name_resolve_bcast: Attempting broadcast lookup for name ���_<0x20>
convert_string_allocate: Conversion error: Incomplete multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(���_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(��_)
convert_string_allocate: Conversion error: Illegal multibyte sequence(�_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence(▒_)
convert_string_allocate: Conversion error: Incomplete multibyte sequence)
convert_string_internal: Conversion error: Incomplete multibyte sequence(���_)
convert_string_internal: Conversion error: Illegal multibyte sequence(���_)
convert_string_internal: Conversion error: Illegal multibyte sequence(��_)
convert_string_internal: Conversion error: Illegal multibyte sequence(�_)
convert_string_internal: Conversion error: Incomplete multibyte sequence(▒_)
convert_string_internal: Conversion error: Incomplete multibyte sequence)
Connection to ���_ failed

Feisty configuration is completely default, with 1 added share samba pointing to directory /samba, allowing only guest connections)