The next release of Debian stable will have Python 2.6 as default and it is expected for the first weekend of February, so it is safe to start with Python 2.6 right now.
True. However keep in mind who uses debian stable... people who won't jump on squeeze the moment it gets stable. It will still take months before the situation really changes. But yeah - I agree that 2.6 is pretty much safe for new stuff.
People who use Debian stable also aren't going to use your new library anyway. They're not running stable because they want to install a bunch of recent stuff, after all...
Why wouldn't they? I had to choose which version to target when writing some software lately. The production was debian stable yet I wanted to release the project for others. In the end I have to keep 2 branches - one for 2.X and another for 3.X - it was a trivial piece of code, so it's not a big problem, but I can imagine how silly it must be for bigger projects.