Before going through a lot of trouble diagnosing, have you handled the common cases?
1. For one, are you sure you're not hitting some sort of connection limit?
a. What sort of connection are you getting? Are you creating a vanilla JDBC connection, or are you getting one via a connection pool?
b. How many connections is the pool allowed to grow to?
c. How many connections will the DB server actually allow?
d. Regarding JDBC connections, are you closing the connection each time you're done?
#a to #b should be easy to diagnose via the app server, if you're using one.
#c should be answerable by the DB admin (or trial & error if you don't mind an angry admin
#d requires a bit of code look-through.
2. Perhaps not so likely, any chance you're running into some sort of networking issue or proxy/firewall issues? This has happened to me a few times, in a clustered scenrio when we create a new secondary box.