||What are you entering for the service?
This error message is usually generated when you type in a name for the service which does not exist in the local windows services file (%systemroot%\system32\drivers\etc\services). If the other machine you are attempting to connect from has a service name with the correct port number established, this would explain why connections work from one machine, but not another.
If you use a name for the service, like 'esri_sde', then you must have an entry in your local services file that corresponds to the port number that the ArcSDE service is listening on. The entry would look something like this
esri_sde 5151/tcp #ArcSDE service
I'd recommend typing in the port number rather than a service name - that way you don't have to maintain a service name locally, and there is much less opportunity for error.
More information can be found here: http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=Creating_spatial_database_connections