Here's the ULTIMATE test. ULTIMATE test.
Step 1: In skin viewer or in AH hangar save the default skin.
Step 2: Go to /skins/ directory and copy and paste (as-is) the entire directory named "109e4" -- you should now have a "Copy of 109e4" directory.
Step 3: WithOUT changing anything inside it, rename the folder "109e41" or "109e43" or whatever you wanted to use.
Step 4: open the 109e4.txt file inside this directory, change it so you can distinguish it from default.
Preview in-game.
If it doesn't work e-mail HTC or post in bugs forum.
If it shows up, the problem is not the directory structure, but rather what you are putting into the structure. If the hangar allows you to choose this skin, that means the way you were saving the bitmap before was not working.
In photoshop: 2 schools of thought. You work in RGB, that's a given. Flatten all layers, select Image > Mode > indexed, select adaptive palate and 8-bit (or enter 256 colors manually). Save file as 8-bit bitmap. Try again, should work. Second option flatten all layers, select File > Export > Bright and give it the proper export name.