As far as I am aware this is not plugin related. I have had this problem myself with a very trimmed down system and certainly with none of my own plugins activated. There does seem to be some weird logic on the Write > Page and Manage > Page panels that sometimes shows and sometimes hides the template box. I have never worked out what that logic is.

My advice would be, in the first instance to check the php header of any page templates you have to ensure they are formed correctly - that is what WP is looking for after all - and if you don't get the box on a New Page write then go talk on the WP support forum.