Linux lets you delete files that are in use, but the space is not actually freed until they stop being used. So I guess what happened is you deleted some apps that were still being used (or hadn't closed properly), so you didn't see the extra space until after you had rebooted.