Many of the methodologies used in the early phases of user centered design, such as card sorting and paper prototyping, are not accessible to people with disabilities. Anybody have any advice on alternative methods that can be used to include users with disabilities in these early phases of UCD?
Depends on the person. Depends on the disability. Ask them :-)
For example I've done card sorts with people with visual impairments. After some conversation we ended up using bigger sheets of paper, thick pens and a large table (with the occasional verbal reminder). Worked well.
I'd guess that similar "scale it up" techniques would work reasonably well for a bunch of visual/physical impairments.
We also tried to use some swell paper for site maps (it's a kind of paper that you can print on then run through a sort of heating device that raises the black bits so you can detect them by touch.) That didn't really work though.. went back to just talking it through.
Also did some tests where I "pretended" to be a text-to-speech browser - which was interesting.... but I don't think I'd had enough experience at the time with how they worked to make it as useful as it could have been. Would probably have been simpler to mock some XHTML and run it through that way - but I didn't come with the necessary hardware at the time.
First, define your personas, including, for example: blind and highly technical, blind and unfamiliar with my product, sighted but keyboard only user, visually impaired but not blind, deaf and technically-savvy, deaf and not technially-savvy, etc.
Understanding those personas specifically should enable you to devise tests as needed, just like other personas (you wouldn't ask a child to tell you if your car buying website was easy to use because that data is nearly irrelevant). For example, if you want to know how a visually-impaired person would respond to the IA of your site, just create cards with extremely large font, or use an online card-sorting tool such as Optimal Sort. If you want to know how a blind person would respond, send then an email with the IA organized in header-structured outline because that is what they hear through screen-reader technology.
But first, clearly identify WHY you are asking someone with a specific disability so that you are asking the right questions.
Well as adrianh pointed out it depends on who your user base is and what is "disablity" you are looking at. I have found that certain methods work better with certain groups:
People with spinal cord/muscular disablities : I have found that Participatory design to be very useful in working with spinal cord/muscular disabilities as they are often willing to provide inputs on why specific designs would work and how they would like a specific design to be. The act of involving them at an early stage also allows the researcher insight into the challenges faced by them and the unique methodologies used by them face those challenges.However, I have found that usability testing is greatly disliked by most people with disabilities (unless they were part of the design process) as they consensus is that the design was implemented without considering the issues faced by them
Visually impaired people : If you are just trying to gather information about a potential application,standard methods like interviews work just great.However you should be aware of the challenge of trying to depict the functionality of the application to them.however if needed,initial usability testing can also be done by the use of screen readers to which would help the user in navigating around the application.Also look at options of providing braille cards for card sorting if that's an option for you.This is a good read: Usability Tips and Tools for the Visually Impaired on the Web
Deaf people : You can conduct standard usability tests or card sorting exercises but ensure that the objective of the exercise is communicated clearly through written text or by the user of visual graphics which clearly explain what the user is expected to do to achieve what goal.Also ensure you have plenty of spare materials (papers,post it notes) around which can be used to communicate what you are trying to do and what you would like them to do next
I haven't worked with mute people or got the opportunity to observe any of my professors/friends work with them so I cant comment on what works and what doesn't but I would imagine that communication would be the key driving factor and the users should be provided with material which would help them communicate by using their other senses such as eyes,years and physical actions such as writing it out or even acting it out.
Great Question !
These are some excellent links I found with regards to interacting with people with disabilities while working with them :
Just to state here some of the research projects we are following on our FeedBot project , we would like to contribute with further information. The projects are related to people with Upper Mobility Impairment or Cerebral Palsy that are highly dependent and need assistance support. That said, several research projects are being developed to help those who live in limited conditions.
On the JACO project, the authors produced a research paper titled as Evaluation of the JACO robotic arm  showing the results of 34 participants with disabilities. The goal of the study was to evaluate the efficacy, safety, and relevancy of the JACO robotic arm. Therefore, the authors concluded that it is an alternative for increasing the autonomy of individuals with upper extremity disabilities. Where projects like this, will show us how to involve measurement of the time needed to execute specific tasks and evaluating easiness of control.
The FeedBot  is a project that proposes to research, as well as develop, a fully autonomous mobile arm capable of feeding people with disabilities, as tasked by a Vision System. With its autonomy and learning, we foresee that FeedBot  will have a great impact in the quality of life of people with a wide range of motion-related disorders, such as Parkinson’s disease, cerebral palsy, or stroke. At the moment, we are doing some questionnaires regarding user characterization. One potential method to follow is to measure both acceptability for the entrance of a robotic arm on daily meals, and improvements on quantitative and qualitative results.
 Maheu, V., Archambault, P.S., Frappier, J. and Routhier, F., 2011, June. Evaluation of the JACO robotic arm: Clinico-economic study for powered wheelchair users with upper-extremity disabilities. In 2011 IEEE International Conference on Rehabilitation Robotics (pp. 1-5). IEEE.
 Silva, C., Vongkulbhisal, J., Marques, M., Costeira, J.P. and Veloso, M., 2017, September. Feedbot-a robotic arm for autonomous assisted feeding. In EPIA Conference on Artificial Intelligence (pp. 486-497). Springer, Cham.
"people with disabilities" is rather a very undefined user base. Usually the "standards" of disabilities minimum are dictated by govs for public sites, but those are usually also very irrelevant for actual use. Maybe we really need a definition (or standard?) of what really a "disabled" web user is. As of my experience disabled in web design translates to screen-readable. In this case usability testing is as simple as installing screen-reader and using it no-eyes.