UPDATE: I wanted to follow up in case anyone comes across this in the future. I did some more digging on ICP code created on MATLAB file exchange and found that most of the limitations arise when the rotations and/or translations are very large, then the algorithm cannot solve well. So, using the code above, I changed the angles to be 44.9, 90+44.9, etc. and found that the algorithm worked perfectly. So, it seems like 45deg is too large of a rotation for this problem.
For my research, my plan is to try to align the two point clouds manually, and then use pcregistericp to fine tune the registration. Then the translations and rotations should be small enough for the algorithm to work. I'm happy to hear other suggestions, though!