WAN overload?

Our servers have been performing poorly for some time and I find
downloading a test 1M file is erratic. The ISP says that there is
nothing wrong with their network and that it must be our hardware
(though we have the same problem on two independent sets of hardware
behind two firewalls on two IP addresses on their network).

Our firewall shows a huge amount of traffic on the WAN port, both in
and out. So it seems the vast majority of traffic is not meant to be
arriving in the first place.

The logs have quite a few odd looking entries, such as:

SAT SEP 30 17:42:59 2006 time="2006-09-30 17:42:25 Sat "
proto=1- icmp packet - Source:=217.112.89.236 -
Destination:=85.134.20.121 - [ICMP error message replay attack
detected, dropping packet from WAN n/w]

SAT SEP 30 17:42:59 2006 time="2006-09-30 17:42:25 Sat "
proto=1- icmp packet - Source:=217.112.89.236 -
Destination:=85.136.171.106 - [ICMP error message replay attack
detected, dropping packet from WAN n/w]

and

SAT SEP 30 17:39:07 2006 time="2006-09-30 17:39:07 Sat "
proto=6- tcp packet - Source:=85.234.152.79 -
Destination:=85.185.91.72 - [Invalid TCP packet recieved before 3-way
Handshake is complete Src 139 Dst 1077 from WAN n/w]

SAT SEP 30 17:39:07 2006 time="2006-09-30 17:39:07 Sat "
proto=6- tcp packet - Source:=66.29.25.83 -
Destination:=85.234.133.161 - [Invalid TCP packet recieved before 3-way
Handshake is complete Src 41993 Dst 22 from WAN n/w]

amongst others. I have also seen "smurf attack" mentioned in the logs.
I have tried to read around the subject a bit but am really at a loss.
Is this large volume of WAN traffic that does not get through to our
server likely to be causing the performance issues and what can we or
our ISP (colocated servers) do to put things right? The volume of WAN
traffic is several Gigs a day that has nothing to do with legitimate
requests that come in.

Thanks for any help or pointers
John