Unable to get a database connection while deleting rows

I have a java application receiving data from a thousand devices on
periodic basis.
When receiving data the application gets a database connection, inserts
a row and closes the connection again.
If this process takes more than 15 seconds, the device assumes the
connection dead and makes a new one.

Sometimes a device is taken out of production and the data from it is
deleted.
Deleting ex. 30000 rows of a total of around 30 mill. takes about 45
seconds.
I expect this to be a row locking process and there is also no problem
with inserting rows while this process is running.
The problem is that getting the database connection can take from 1 to
the full 45 seconds.

There is nothing in the log telling me what's going on except from a lot
of "unexpected EOF on client connection"

Can anyone bring a light on what resource that can be the bottleneck ?

The system is "PostgreSQL 8.1.8 on x86_64-pc-linux-gnu, compiled by GCC
gcc-4.0.gcc-opt (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5)"

Thanks in advance,
Poul