I'm wondering if anyone has come across this before. To achieve PCI-DSS compliance, we have been forced to segment our network behind a firewall.

Previously, our SQL server was on the same IP range as our clients (10.0.0.0/24), but has now been moved to a different IP range (192.168.4.0/24). The firewall, as far as I can tell, has been properly configured. All clients on the 10.0.0.0/24 range can ping the SQL server by name or by IP address.

However, when I try and configure clients to connect to the SQL Server by ODBC, I get the same error:

Connection failed.
SQL State: '01000' SQL
Server Error: 10061 [Microsoft][ODBC SQL Server Driver][TCP/IP Sockets] ConnectionOpen (Connect()) 
Connection failed:
SQLState: '08001'
SQL Server Error: 17
[Microsoft][ODBC SQL Server Driver][TCP/IP Sockets] SQL Server does not exist or access denied.

I've ensured I'm using the correct username and password, and also played about with the client configuration settings (trying named pipes, tcp/ip etc. The port I'm attempting to use is 1433, which has been opened on the firewall).
Can anyone help?

No, but if this has been working since the dawn of time and stopped when the firewall went into place, that's definitely what's going on. Strange that it responds to a ping, though, it's clearly reachable from the client, and the error you're receiving means it hasn't even got to authentication yet, so it's nothing to do with SSPI.

How is the ODBC connection set up?

telnet ip port
see if it connects