Just had a quick browse of the Firebrick manual - do I detect a touch of the A&A "NAT is Evil" viewpoint?
Anyway I was considering not the path from your devices to the modem, but the return. Let's say your device was x.x.x.x/26, and the D-Link modem has it's default IP settings of 192.168.1.1/24 and just for illustration we've configured the FB interface as 192.168.1.2. The Firebrick will see both these subnets as directly attached, and from what you say it will route between them without explicit configuration. So your packet from x.x.x.x will reach the modem, but how does the modem know how to route back to x.x.x.x? What I'm suggesting is to NAT your source address, so that the packet hitting the modem appears to originate from 192.168.1.2, which is on the modem's local subnet and therefore reachable directly. Does that make sense?
In Cisco terms (sorry) you'd mark your LAN as "inside", the interface to the modem as "outside", then you'd configure inside source nat.
If you can configure the modem (in this example) with a default gateway of 192.168.1.2 then NAT is not required and it's just plain old routing.