Me parece que el cliente Bitcoin te está avisando de que la transacción que has ordenado junto con su correspondiente comisión supera la cantidad de bitcoins que tienes en la billetera.
Comprueba en las opciones del programa si la cantidad de comisiónes para cada transacción es conforme a tus intenciones.
Otra cosa que puede sucederte es que estés intentando hacer una transacción desde una dirección que ha recibido bitcoins muy recientemente. Si no recuerdo mal el cliente Bitcoin está diseñado para añadir comisiones más altas de las especificadas en las opciones cuando una dirección acaba de recibir Bitcoins e intenta enviarlos de nuevo muy pronto. Esto se ha diseñado así expresamente para evitar el bombardeo de transacciones spam en la cadena de bloques. Cuanto más próximas entre sí estén las transacciones en el tiempo a/desde esa misma dirección, más comisiones tendrás que pagar para que sea aceptada.
Me imagino que será esto último lo que te estará pasando. Si acabas de recibir btcs en una dirección e intentas reenviarlos a otra dirección inmediatamente el cliente bitcoin intentará cargar comisiones superiores a las que tienes seleccionadas. Y ahí llegamos al mensaje que te devuelve el cliente.
Prueba a esperar unas horas a realizar la transacción o paga un poco más de comisión por spamear la cadena de bloques.
Mira lo que dice en la wiki:
"Transaction fees
Miners have no obligation to include transactions in the blocks they try to solve. The client can associate a transaction fee with any transaction, giving miners an incentive to put the transaction in a block, as miners collect the transaction fees associated with all transactions included in blocks they solve. Very small transactions, or those that use relatively new coins, have low "priority" and the network may require a transaction fee to reduce spam. Most bitcoin clients, including Bitcoin-Qt version 0.5.2 (beta), enforce a minimum fee for low priority transactions of 0.0005 BTC."
Tomado de esta dirección:
http://en.wikipedia.org/wiki/Bitcoin