Modifiers work on the mesh.
The orientation of the default cube is "logical". With (0, 0, 0) rotation it sits "flat". It all makes sense. Start to rotate in edit mode (or in object mode and apply) it all starts getting a bit hard to follow.
Modifiers work on the mesh (data) part of an object. A couple of ways to change the orientation of the mesh before using the array modifier.
1. Armature Modfifier before the array modifier.
If the armature modifier rotates the mesh before the array this'll work.
Rotating the bone, and result on cube 16 x 16 array
Here I've added a single bone middle of default cube, selected cube, ⇧ Shift selected bone, ⎈ Ctrl P set parent, and chosen automatic weights. Now rotating the pose bone rotates the cube. If the armature modifier is before the array modifier it will do what you want, ie rotate each cube in the array.
Keep the normal orientation of cube as the Basis key. Add a shape key(s) for the rotated state(s). Because shape-keys are moving the vertices (data) of the mesh, this will give desired result too.