Должна ли программа, использующая gpl-библиотеку, издаваться под лицензией gpl?

В общем случае да, должна; см. параграфы 3 и 6 GPLv2.

Могу ли я распространять исходники под лицензией BSD, если не включать библиотеку в поставку? Если я буду делать компиляцию через py2exe, не будет ли проблем с лицензией?

Боюсь, что не можете; будут проблемы. Некоторые подробности по ссылкам: 1, 2.