That is exactly the issue. If you really want to solidify the carbon for long term storage, you'd have to spend more energy than you gain in the first place. At least I'm not aware of a process that could capture CO2 for long term storage with only a fraction of the Carbon-to-Carbon binding energy (which is what you gain when burning, minus the C-O2 binding.