Our main WINS server is scheduled to be decommissioned, and the WINS service was turn off a few weeks early unknown to us (Network Support). We started to get random users complaining that they couldn't get to computer resources by name. We found that the commonality of the devices was that they were not joined to the Windows domain (no Dynamic DNS) and did not have DNS entries for their names on our non-Windows DNS servers.
Adding the DNS entries fixed the problems. I found the following page at Microsoft's site very useful in figuring out the problem:
http://support.microsoft.com/kb/172218
At my previous job, we had no problems disabling NetBIOS entirely as we had one department that controlled the servers, workstations, and network, so we didn't run into a case where users lost functionality because we made sure everything resolved correctly before disabling the service. I vaguely remember having an issue with one of our flexLM license servers because the version used was so old, it didn't use DNS to resolve names. Updating the version fixed the issue.
So as long as you communicate to users that the functionality is going away and let them know what they need to do to get around it or fix it, I don't see any problem with doing away with it.