I installed Ubuntu 13.04 a few weeks ago as a fresh install on my laptop. 64 bit, using full disc encryption.
Suddenly this message appears when updating the software.
I looked in GParted, and sure enough there is a separate partition with /boot on, which is only 243MiB. This is the first partition, on the drive - all following space is used by the encrypted filespace, which to me means that simply giving the /boot partition more space would be a tough task...
Here's a screenshot of my partitions. Note that this is unaltered from the standard automatic install setup... the only thing I did differently is choose to use full disc encryption.