Need to NAT incomming packets

["Eric Plikuhn" <ericgate@imagestream-is.com>]

I trying to determine if the following can be done.  I've searched for a
solution but can not find it... because most people are not forced to
attempt this.

Here is the scenario:

Site A  10.0.0.0/8
   ||
   ||
Core Router==========Internet
   ||
   ||
Site B  10.0.0.0/8

My problem is that the Site A and B router don't/can't do NAT.  The second
problem is that they MAY be using the same IP addresses at both sites.  Each
site was giving the 10.0.0.0/8 private network to do work with and they have
IP address all over it.

I was hoping have a SNAT rule for each incoming interface in the prerouting
chain on the Core router....  but you can't do SNAT in prerouting with
iptables.

I'm thought of a few possibilities, but so far they all fall short.
Assuming that I can't get new routers at the Site locations and they may be
using the same IP's what can I do?

Eric