That is strange. I just tested it with a new address, it worked fine.
Can you give me some details please?  Did you sign using QT or coinomi