After a lot of troubleshooting, I've finally resolved this issue. I believe that many Windows users will encounter the same problem, so here's how to get pybitshares working on a Windows PC:

(Some of these steps are probably unnecessary... but I can't be sure which ones are the most important)

First, install Visual Studio Community 2017 (https://www.visualstudio.com/downloads/)
Even if you've already installed this previously, there are updates that may be required, as new components have been added recently. To do this, search the start menu for "Apps & Features", find Visual Studio Community 2017, and click "update". When that's done, click "modify".
Make sure that you select the "Individual Components" tab, then scroll down to "Components, build tools and runtimes".
These are the components that I have selected (you definitely don't need all of these - but this combination works for me):

    C# and Visual Basic Roslyn compilers
    C++/CLI support
    MSBuild
    Python 2 32-bit (2.7.14)
    Python 2 64-bit (2.7.14)
    Python 3 32-bit (3.6.3)
    Python 3 64-bit (3.6.3)
    VC++ 2015.3 v140 toolset for desktop (x86,x64)
    VC++ 2017 v141 toolset (x86,x64)
    Visual C++ compilers and libraries for ARM
    Visual C++ runtime for UWP
    Visual C++ tools for CMake
    Windows Universal CRT SDK

Once all those are selected, click "Modify".

Then, from the start menu, search for "x64 Native Tools Command Prompt for VS 2017". Right click it, and "Run as administrator" (IMPORTANT!). Then run the following commands:

    pip uninstall bitshares
    pip uninstall pycryptodome
    pip uninstall cryptography
    pip install cryptography
    pip install pycryptodome
    pip install bitshares

You're done! pybitshares should now work correctly!

Why does this work?
I believe that the pycryptodome and/or cryptography installs can be broken if you don't have the correct Visual Studio Compiler Tools installed and added to the PATH environment variable. Any attempt to update these tools later will appear successful, but the initial install remains broken. The type of error messages you will see when you first try to install pybitshares will be similar to:
    "cl.exe failed with exit status 2"
    "error: command 'cl.exe' failed: No such file or directory"
    "Cannot open include file: 'openssl/aes.h': No such file or directory"
    ...and other openssl related errors.

Oddly, with a broken install, all the pybitshares commands will still work - but any command that sends information to the blockchain will take 10 - 20 minutes instead of 1 - 2 seconds.

I hope this helps somebody!

Check this:
https://bitsharestalk.org/index.php?topic=26072.0
https://bitsharestalk.org/index.php?topic=26083.0

Thanks, after reading through some recent forum posts, I was just about to post the first link. I hadn't found the second one yet. In my opinion, changes like this need to be announced somewhere prominent before being implemented. Is there somewhere like this that I'm not aware of? I do understand that this was being discussed on the forum, but most users aren't following all the topics every day, and the thread titles don't suggest that any decisions were finalized.

I've also got an issue with Ethereum that failed to withdraw.

What cryptocurrency are you all using when you withdraw now? Have you got a reliable method?

I Assume you're talking about the private keys.

Your password in combination with your account name is used straightaway to generate your private keys. So you won't be changing your password (in settings, that one is on the left, under accounts)

These keys are used to let you log in from any computer and also for sending encrypted messaging

Thanks fx4all. So I can use my account name and any private key I've generated, to login to my account with any browser, and I can also use my account name and password to do the same thing? If so, is it possible to remove the original password that was used when creating the account?

I've tried to use the "Add password generated keys" option to create new keys. When I click "Publish Changes", it asks me to confirm the transaction,  and when I click confirm, it says "Failed to broadcast the transaction", regardless of what combination of new active/owner/memo keys are selected to be used. I do have enough BTS for the fee. I'd paste the error message, but it seems to contain my old and new keys...

The system is complicated, it's not just you.

I'm not sure if this will help you - I've only used the web based account model:
Click the gear icon in the top right -> settings -> accounts -> view keys -> owner permissions.
There will be a long code under account/key/address - this is your public key. Click this key - it will then bring up the "Private Key Viewer" window. Click "show" to see your private key.

Don't share your private key, be very careful with it! I can't comment on whether you should use the private key for what it is you want to do - hopefully somebody else can help you there.

Is it slow when you use Uptick (http://uptick.rocks)?

I tried installing uptick to test this, but got errors with the pip install and the manual install, even after installing Visual C++ Build Tools. I'll troubleshoot further tomorrow.

FYI - the last few lines of the failed install:
Writing C:\Users\xxxxx\AppData\Local\Temp\easy_install-t2ll6vmc\scrypt-0.8.0\setup.cfg
Running scrypt-0.8.0\setup.py -q bdist_egg --dist-dir C:\Users\xxxxx\AppData\Local\Temp\easy_install-t2ll6vmc\scrypt-0.8.0\egg-dist-tmp-rlrb2hdn
scrypt.c
scrypt-1.2.0/lib/crypto\crypto_scrypt.h(33): fatal error C1083: Cannot open include file: 'unistd.h': No such file or directory
error: Setup script exited with error: command 'C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\BIN\\x86_amd64\\cl.exe' failed with exit status 2

Hi everyone. I've been trying out the pybitshares API and can get it to do almost everything I need. However, when I buy or sell on the market, it takes between 10 and 20 minutes before the transaction shows up. During that time, python is using a lot of CPU. Am I doing something wrong, or is that normal? Market queries etc are instant. Buying and selling with the web interface is also instant. When I added the private key, it also took several minutes (I thought python had crashed, and I restarted it a few times, before allowing it to finally add the key).

Here's what I did:
I created a new account (account model) using my browser, then created a new wallet using the pybitshares API, then imported my private key (bitshares.wallet.addPrivateKey('xxxxx')).

Below is the code that produces the problem.
from bitshares import BitShares
from bitshares.market import Market
from bitshares.price import Price
from bitshares.amount import Amount
from bitshares.account import Account
import time

account = Account("xxxxx")
Node1="wss://bitshares.openledger.info/ws"#Nuremberg, Germany
bitshares=BitShares(Node1,nobroadcast=False)
market = Market("BTS:USD")
print(market.bitshares.wallet.unlock("xxxxx"))
USD_Bal=account.balance('USD')
print('Buying BTS')
print(market.buy(\
    Price(0.115, "USD/BTS"),\
    Amount(USD_Bal/0.115*0.5, "BTS"),\
    account="xxxxx",\
    returnOrderId='head'\
    ))
I've tried without the returnOrderId='head' setting, it's still slow. Any ideas?