VBA Excel 2010 Array size limitations

I have recently needed to perform calculations with rather large arrays in VBA Excel 2010. However, to my dismay, both my computers at work and home (one is a PC and the other a Mac (The PC has 8GB of RAM and the Mac has 4GB)), keep throwing the same Out of Memory error when I try running my program. This led me to running some tests to get to the bottom of the issue.

Sub Test1()
    Dim arr1() As Byte, arr2() As Long

    ReDim arr1(1 To 268000000)  ''These work
    ReDim arr2(1 To 268000000)
End Sub

Sub Test2()
    Dim arr3() As Byte, arr4() As Long

    ReDim arr3(1 To 269000000)  '' Both of these fail
    ReDim arr4(1 To 269000000)
End Sub

Now, according to MSDN, the index of each dimension is limited by (2 ^ 31) - 1. As you can see above, I'm nowhere near that threshold and eerily close to 2^28. According to some crude calculations the amount of memory of each array above are:

arr1:  268,000,000 * 1 = 268,000,000 bytes of memory
arr2:  268,000,000 * 8 = 2,144,000,000 bytes of memory
arr3:  269,000,000 * 1 = 269,000,000 bytes of memory
arr4:  269,000,000 * 8 = 2,152,000,000 bytes of memory

You will notice that arr3 is roughly 1/8th the size of arr2, yet when trying to Redim arr3, we get the out of memory error while Redim arr2 works perfectly fine. What's going on here??? It should be noted that this post, although similar, does not apply as I have plenty of memory on both machines, and is asking simply about memory and not how many elements one can put in an array.