I like to add we're seeing the same problems on a random subset of our equipment. The "storage" referred to is RAM, not disk space.
This is a snippet out of the Setup.log files of an effected PC:
17.09.2015 16:00:52.000 1442520052 (null) GetFileWithRetry: vps_32-1140-113f.vpx downloaded and verified
17.09.2015 16:00:52.000 1442520052 (null) DldPackage: C:\Program Files\AVAST Software\Avast Business\Setup\vps_32-1140-113f.vpx, returned 0x00000000
17.09.2015 16:00:54.000 1442520054 (null) PerformPkgDiff: pPkgDiffStorage->m_pbtBufNew allocated 255477305
17.09.2015 16:00:58.000 1442520058 (null) PerformDiff: Ok
17.09.2015 16:00:58.000 1442520058 (null) HttpGetWinsock(http://192.168.250.14:16135/vps_32-1141-1140.vpx)
17.09.2015 16:00:58.000 1442520058 (null) Used server: http://192.168.250.14:16135
17.09.2015 16:00:58.000 1442520058 (null) GetFileWithRetry: vps_32-1141-1140.vpx downloaded and verified
17.09.2015 16:00:58.000 1442520058 (null) DldPackage: C:\Program Files\AVAST Software\Avast Business\Setup\vps_32-1141-1140.vpx, returned 0x00000000
17.09.2015 16:00:58.000 1442520058 (null) PerformPkgDiff: pPkgDiffStorage->m_pbtBufNew allocated 255563766
17.09.2015 16:00:58.000 1442520058 (null) ERROR PerformPkgDiff: pPkgDiffStorage->m_pbtBufNew == NULL
17.09.2015 16:00:58.000 1442520058 (null) PerformDiff: vps_32-1141-1140.vpx Bad, error code 0x00000008
17.09.2015 16:00:58.000 1442520058 (null) Vpu: C:\Program Files\AVAST Software\Avast Business\Setup\vps_32-1141-1140.vpx, size: 710682. md5: E583217B43A653AB5B3F51E45551D2EB, computemd5 returned 0x00000000, sig: 010F1232F13BBBE6D25C889C81DBB8ED82096E16421DA8687762A28C2E437A49C6CFABA4A2149374 returned 0x00000000
17.09.2015 16:00:58.000 1442520058 (null) PerformDiff( vps_32, 1140, 1141 ) failed 0x00000008
17.09.2015 16:00:58.000 1442520058 (null) Error:Not enough storage is available to process this command.
If I read this correctly, the problem appears to be that the updater tries to allocate two ~256 MB blocks of RAM and gets denied by the OS on the second block. This particular box has 3GB installed of which 1.5 GB was free at the time. The failure could be due to memory fragmentation, but even after a reboot, the update still fails.
(I guess it is time to update the stated "only 128MB RAM needed" in the minimum system requirements...)