When you replaced the himem.sys, did you replace all instances of it? Himem.sys should be located in the following places:
C:\
C:\WINDOWS
Also, check the config.sys for the proper line, as listed below:
DEVICE=C:\WINDOWS\HIMEM.SYS
Also, for further verification of your himem.sys file, the exact file size is:
33,191 Bytes
Good luck, and if I think of anything else, I'll let you know.