My two cents. On my company (B767 mainly), we used to have issues with APU starting.What we've understood was if after you put the switch to ON, allow a few seconds, when advancing the spring loaded to Start, you do it slowly and gently until you see the RUN RUN and then gently "walk" the button back to the ON position. We don't release it. The fingers are allways in the button.
As we must comply with ETOPS regulations, monthly and on each aircraft we need to do a inflight start and cruise level.
Using the method above, we've been able to start APU on a single attempt. At cruise level you cannot get more cold and soaked...