First: I wouldn't bother with cleats on your current bike. Honestly, I didn't find they made much of a difference on any of my bikes. Here's a fun article about cleated pedals and shoes:
http://www.rivbike.com/kb_results.asp?ID=45
That was an interesting read! Thanks, and I guess I'll hold off on this gear.
Second: tight shoulders could be from bike fit or from locking your elbows or even from slouching. Try unlocking your elbows first, particularly as you get tired. If that doesn't help, ask someone for some assistance with fit.