YES!
Finally gotten this to work.
I did everything at the start of this thread except I put wins AFTER dns in nsswitch.conf rather than the beginning. Putting it at the start gave me more problems than it solved, mainly because it caused aMSN to stop working entirely and seemed to slow my internet right down.
It also turns out that adding a netbios name under workgroup in the config file is also essential, as windows doesn't allow ubuntu access to it's shares without one.
For anyone else who is having this same issue, here's the sections of my config files that I edited;

/etc/samba/smb.conf

#======================= Global Settings =======================

[global]

## Browsing/Identification ###

# Change this to the workgroup/NT-domain name your Samba server will part of
workgroup = MSHOME
netbios name = compist-desktop

# server string is the equivalent of the NT Description field
server string = %h server (Samba, Ubuntu)

# Windows Internet Name Serving Support Section:
# WINS Support - Tells the NMBD component of Samba to enable its WINS Server
# wins support = no

# WINS Server - Tells the NMBD components of Samba to be a WINS Client
# Note: Samba can be either a WINS Server, or a WINS Client, but NOT both
; wins server = w.x.y.z

# This will prevent nmbd to search for NetBIOS names through DNS.
dns proxy = no

# What naming service and in what order should we use to resolve host names
# to IP addresses
name resolve order = lmhosts wins bcast host



/etc/nsswitch.conf

# /etc/nsswitch.conf
#
# Example configuration of GNU Name Service Switch functionality.
# If you have the `glibc-doc-reference' and `info' packages installed, try:
# `info libc "Name Service Switch"' for information about this file.

passwd: compat
group: compat
shadow: compat

hosts: files mdns4_minimal [NOTFOUND=return] dns wins mdns4
networks: files

protocols: db files
services: db files
ethers: db files
rpc: db files

netgroup: nis


Hope this helps people!

Compist