busoni, you need to shut down Poloniex now and try to make your users whole from your own funds and debt. Do not continue trying to run an exchange. Your post mortem indicates that you do not have sufficient programming ability to handle other peoples money - no mention was even made of database transactions, which are a basic "database programming 101" topic. Your proposed fix of checking for negative balances is wrong and indicates that your code is almost certainly riddled with other exploitable bugs.
Please do the right thing and refund everyones outstanding balances, then wind up your operation.
This was my thought too. At the risk of simplifying things too much, a fix for this might be something like (pseudo-codey):
BEGIN TRANSACTION
INSERT INTO Ledger ...
UPDATE UserBalance SET balance = balance + @amt WHERE user_id = @id AND (balance + @amt) > 0
// if previous update didn't update any rows, rollback
INSERT INTO WithdrawalQueue ...
COMMIT
Bonus points if you digitally sign the records in the database with a private key known only to your application to help guard against direct database manipulation.
But as someone writing financial software, he should have known this already. Of course it could just be an oversight on his part (everybody makes dumb mistakes sometimes), but if there are bugs like this, there are likely other data consistency bugs that can be exploited as well.