Long Distance Shift Register
SPI is supposed to be used for things in close proximity to each other. See Wikipedia - Serial Peripheral Interface Bus.


  The Serial Peripheral Interface (SPI) bus is a synchronous serial communication interface specification used for short distance communication, primarily in embedded systems. 


(My emphasis).

At that distance, and at standard SPI speeds you are probably losing signal integrity. The default SPI speed is system clock divided by 4 (that is, 4 MHz). It's not surprising some bits go missing after 40 feet.

See my page about SPI - you can use SPI to transfer to a 595 register (as described here).

(I'm assuming you are talking about a 74HC595 shift register)

I suggest running at a somewhat lower speed - insert delays after toggling the clock pin (each way). Or use the SPI hardware at (say) SPI_CLOCK_DIV128.




  The shift register is very close to some 110V wires. Maybe interference


You might also want to look at a balanced line driver (eg. RS485) - I have a page describing that.




  The 5V power supply isn't powerful enough to power the relay board and the shift register?


The register won't take much power. I trust the relays are solid-state ones and not coils that you are directly driving from the 595 chip?



Also see How do you use SPI on an Arduino?