The feature did work in the past however pages now seem to default to 'Default Template'.
I can see my available page templates in the drop-down on the Page edit page, however after saving the admin simply shows 'Default Template' again.
I have tried disabling all plugins as well as remaking some of the templates, however the behaviour continues.
Note: I'm using latest self-hosted WordPress.
Update: After some digging it would appear that I am getting 'Table xxx/wp_postmeta' is marked as crashed and should be repaired". However running repair through phpmyadmin does not fix the issue.
Update: Rebuilt the table entirely, still have issue.
(Originally posted this question here: http://webapps.stackexchange.com/questions/33627/wordpress-page-edit-does-not-save-selected-template)