I have exhausted all the options listed above...
PURGE! It works. Just purge all the items out of the block's file & save, then update the image on the tool palette.
I had this problem today. I have a block that has many other blocks inside of it. I would remove a few blocks at a time and regen the image. Eventually, the image was the correct size, so then I just had to hunt down the block. After I found it through trial and error I realized I could've just scrolled the the "Edit Block Definition" dialog box and you can see the extents of each block. That particular block has splines which appears to have been causing my issue.
I was going through the same issue i resolved it so what you can do first go to the "insert" by typing i and then there just on the right of the filter there is blue colour block option just click on it and then choose whatever you like extra large icon,large or medium etc.