RAM Utilization
Oops! When you said you increased the addr to 17 bits, I misread that as increasing the data to 17 bits. Sorry for the confusion! Please disregard my previous message.
How wide is your data bus?
The Spartan-3 data sheet says the XC3S1000 contains 432 kilobits of Block RAM and up to 120 kilobits of Distributed RAM. Remember that Distributed RAM is built from logic fabric, so if you use all 120 kilobits, then you won't have any room for other logic.
In case anyone's interested, here's where my previous answer was heading . . .
Each FPGA Block RAM primitive has configurable data bus width: 1, 2, 4, 9, 18, or 36 bits, and various address depths. If your HDL creates 18-bit RAM (and up to 1K words), then ISE XST should infer 18-bit Block RAM. However, older versions of ISE would infer a 16-bit and a 2-bit Block RAM. That's wasteful, consuming twice as many Block RAM primitives as necessary. Newer versions of XST are smarter.