Could you please tell us which theme you are using as this may help other users who may experience this problem.
This more than likely is related to your theme or WordPress settings if it happens when all other plugins are deactivated.
Could you test to see if it happens with the WordPress 2011 and 2012 themes.
If it happens for all themes it could be related to WordPress settings for rewriting links. get_page_permastruct() is a member of class WP_Rewrite and for some unknown reason that hasn’t been defined before this function is called.
link-template.php is a standard WordPress file and it is generally a bad idea to edit this as it may be overwritten on the next upgrade so be wary.
Not sure what your really talking about when you state the following.
However (perhaps related to that) on the page I have [wpuf_edit] that ends up editing its own page page!
If it’s related to the standard WordPress edit link on the bottom of each page the development version fixes this. See the code for wpuf_suppress_edit_post_link() in wpuf_functions.php if you dont want to use the development version.