You have to use avahi-daemon (zeroconf) if you want to connect via a hostname instead of an IP address. From the Raspberry Pi documentation on RPi Advanced Setup:
Install avahi with the following commands on the Raspberry Pi:
sudo apt-get install avahi-daemon
Update boot startup for avahi-daemon
sudo insserv avahi-daemon
Apply the new configuration with:
sudo /etc/init.d/avahi-daemon restart
The Raspberry Pi should now be addressable from other machines as raspberrypi.local, for example:
ssh firstname.lastname@example.org or http://raspberrypi.local if you have HTTP service installed.
If you couldn't connect from Windows PCs via SSH probably you haven't installed the Bonjour service.
Get Bonjour for Windows: Download Bonjour Print Services for Windows v2.0.2. Just install it.