Mac – Time Machine backup taking a loooong time, is this normal

I have run TM backups both locally and across the network.

Moving backups:

Just moving the disk won't work. If you don't need to use the old backups, it's probably worth just biting the bullet and waiting for it to complete a new backup (if you connect an ethernet cable on a gigabit network it's faster (~90MB/s) than connecting the drive via USB (~30MB/s)).

If you need to keep the old backups, you could try creating a sparsebundle with disk utility, mounting it, and then copying the backup files directly onto it. This method would be slower than creating a new backup from scratch over gigabit though, so if you don't need the old backups, it doesn't buy you anything.

Multiple machines:

Yes, you can backup multiple machines to the same Time Machine disk

Try disconnecting all power supplies from the outlet/power source and the device. After 3 minutes hold the reset button down on the AEBS and then connect the power. Continue to hold the reset button down until the light on the front starts flashing amber fast or 5 seconds has elapsed (which ever happens first). If after the factory restore [not hard reset] that if the device doesn't turn on in a minute it's AppleCare time. The AEBS should be covered under the AppleCare Protection Plan of an Apple computer or AppleTV purchased within two years of the AEBS. If they won't swap it out for you, ask for an exception :)