I installed Debian (etch) with the basic install and was able to ping/ssh to the server from my Windows PC using the hostname I set up.

I then installed Shorewall (firewall program) on my Debian server and disabled all incoming ports except SSH.

Now I can't access my Debian server using its hostname, but I can access it using its IP address.

Which service do I need to enable for this to work again?

FWIW, adding the hostname to my Windows box hosts file worked as expected.

no service just add it to /etc/hosts

You mean that you could before you enabled firewall?

It is already in my /etc/hosts file on my Debian server but I don't think that would solve my problem.

The problem is the Windows machine can't resolve the Debian hostname to an IP. Adding something to the Debian /etc/hosts file won't affect the Windows PC will it?

In any case, I swear this was all working before I installed Shorewall so I must have closed off port.

I'll try turning Shorewall off and trying it again.

This is of course an option.
Of course setting an entry in your Debian /etc/hosts doesn't have a effect on the host resolve name of windows.
Also It's maybe an option setup a samba server to act as wins server.
And you could try enable NETBIOS over TCP/IP within Win.

do you have DNS servers configured on ur Windows PC? What are they?
Seems like windows pc can't resolve ur linux box name.
in context of installing firewall i can guess that ur win PC tries to query dns server installed on ur Linux PC and cannot because of firewall, but it is only guess.

Windows can resolve names via three methods - dns, netbios, local hosts files. to answer newbios queries linux box should have samba installed.

anyway, you can add an entry to hosts file, but on your _Windows_ pc. it is located at $windir$\system32\drivers\etc\hosts (where $windir$ - folder where your copy of windows is installed). and this should solve the name resolution trouble.