GCC's ld tries its best to find the correct library to link against. As far as I know, it considers -mcpu, -mthumb, -mfpu, and -mfloat-abi (see examples below). This list may not be complete, -mthumb-interwork is probably considered as well. If -mcpu is specified, the architecture is derived from that value.
So these options should be passed down to ld, and you ought to checked that ld really picks the correct multilib.
For each of these options there are built-in default values which may not lead in the right direction.
If ld cannot find a matching library, it falls back to the default one. There is no error message.
So in your case - assuming that you have passed -mcpu to ld and your toolchain installation is correct - there is possibly no matching multilib, and ld uses the default one. The linking process technically succeeds, but you do not get what you want.
Some examples (arm-none-eabi-gcc 4.6.2)
Available multilibs:
$ arm-none-eabi-gcc -print-multi-lib
.;
thumb/arm7tdmi-s;@mthumb@mcpu=arm7tdmi-s
thumb/cortex-m0;@mthumb@mcpu=cortex-m0
thumb/cortex-m3;@mthumb@mcpu=cortex-m3
thumb/cortex-m4;@mthumb@mcpu=cortex-m4
thumb/cortex-m4/float-abi-hard/fpuv4-sp-d16;@mthumb@mcpu=cortex-m4@mfloat-abi=hard@mfpu=fpv4-sp-d16
The default
$ arm-none-eabi-gcc -print-multi-directory
.
If a multilib for a given cpu is not found, it uses the default as well - there is no error message:
$ arm-none-eabi-gcc -print-multi-directory -mcpu=arm926ej-s
.
There is no error message, even if the -mcpu is "obviously" wrong (that is the cpu is not in the list of known ARM CPUs which you can see with arm-none-eabi-gcc --target-help):
$ arm-none-eabi-gcc -print-multi-directory -mcpu=xxx
.
Even with -mcpu=cortex-m4, the invalid multilib is chosen. cm4 only supports thumb, so this value could be derived from -mcpu, but the built-in default wins:
$ arm-none-eabi-gcc -print-multi-directory -mcpu=cortex-m4
.
To get the correct multlib for cm4, -mthumb is necessary as well, this is necessary to override the default value for the instruction set:
$ arm-none-eabi-gcc -print-multi-directory -mcpu=cortex-m4 -mthumb
thumb/cortex-m4
To get the correct multilib for cm4 with HW support for floating point operations, -mfpu may not be enough:
$ arm-none-eabi-gcc -print-multi-directory -mcpu=cortex-m4 -mthumb -mfloat-abi=hard
.
It requires
$ arm-none-eabi-gcc -print-multi-directory -mcpu=cortex-m4 -mthumb -mfloat-abi=hard -mfpu=fpv4-sp-d16
thumb/cortex-m4/float-abi-hard/fpuv4-sp-d16
Further details regarding multilib can be found here and in auselen's answer
As auselen already commented, the easiest way to resolve this is to find the right toolchain, as building an ARM toolchain is another story.