Did you try splitting the transaction into 2 or 3 as per nc50lc's post?

BTW if you intend to send someone bitcoin now you don't necessarily have to send to your own address first. You can send to the recipient's address in 2-3 smaller transactions instead of one large one.