It's some kind of glitch in their online database. Sometimes it is on a rural route, but I have had addresses it won't accept that are in cities.
The other nice thing about stamps.com is that the address block is just one square instead of a form for each line, like on usps.com. It is loads faster. Except for international, which is still wiggy. I have figured out that for international on stamps.com, you need to put the city, province, and postal code on the same line with no commas, country spelled out on the next line, then let the software keep the province on the same line as the city. It goes through okay then.