I'd imagine you could move all your photos to another host but use the same folder structure. Then on APF there must be for admins a search and replace function to bulk change URLs to the new location.
Good news is that images can still be seen by right clicking on the image and open it on new tab.
Your suggestion of moving them using same folder structure; etc. and then do a search/replace is a good idea. The search/replace can even be done directly on database so the difficult task is to pick the images...
Totally possible with some script-server code (PHP, ASP), here it is explained:
a) Use PHP to search on your database and get all photobucket URLs, automatically save them in a raw file
b) Then for each URL, do a PHP CURL call to download the images and automatically save it on your server (using the same structure or another structure). Then put the new URLs next to old one in the raw file (use a distinctive separator)
c) Use PHP to replace old URLs with new URLs in all post
Job is done.